leetcode-study/coin-change/bky373.java at main · DaleStudy/leetcode-study · GitHub

22 lines (21 loc) · 621 Bytes

// time: O(n * m), where n is the amount and m is the number of coins

// space: O(n)

class Solution {

public int coinChange(int[] coins, int amount) {

int max = amount + 1;

int[] dp = new int[amount + 1];

Arrays.fill(dp, max);

dp[0] = 0;

for (int i = 1; i <= amount; i++) {

for (int j = 0; j < coins.length; j++) {

if (coins[j] <= i) {

dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);

}

if (dp[amount] > amount) {

return -1;

}

return dp[amount];

}

Expand file tree