322. Coin Change#

Recursion with Memoization#

 1class Solution {
 2  private Map<Integer, Integer> memo = new HashMap<>();
 3
 4  public int coinChange(int[] coins, int amount) {
 5    return dp(coins, amount);
 6  }
 7
 8  private int dp(int[] coins, int n) {
 9    if (memo.containsKey(n)) return memo.get(n);
10
11    if (n == 0) return 0;
12    if (n < 0) return -1;
13
14    int res = Integer.MAX_VALUE;
15
16    for (int coin : coins) {
17      int subProblem = dp(coins, n - coin);
18      if (subProblem == -1) continue;
19      res = Math.min(res, 1 + subProblem);
20    }
21
22    memo.put(n, (res == Integer.MAX_VALUE ? -1 : res));
23    return memo.get(n);
24  }
25}

DP#

 1public int coinChange(int[] coins, int amount) {
 2  int[] dp = new int[amount + 1];
 3
 4  for (int i = 0; i < dp.length; ++i) {
 5    dp[i] = amount + 1;
 6  }
 7
 8  dp[0] = 0;
 9  for (int i = 0; i < dp.length; ++i) {
10    for (int coin : coins) {
11      if (i - coin < 0) {
12        continue;
13      }
14      dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
15    }
16  }
17
18  return dp[amount] == amount + 1 ? -1 : dp[amount];
19}