Problem & Approach

  1. Coin Change I

    1. Let dp[i][amount] to be the fewest number of coins among from 0 to i-th coins that makes up to amount. So, dp[i][amount] = min(dp[i - 1][amount](not use i-th coin), 1 + dp[i][amount - coins[i]](use i-th coin)). More importantly, as for dp[i][amount] could be updated by dp[i][amount - coins[i]] rather than dp[i - 1][amount - coins[i]], that’s because every coin can be used for many times.

    2. To decrease the space complexity, we can make the dp[i][amount] to be dp[amount]. Because every time, dp[i][amount] is updated only by i-th subarray or (i-1)-th subarray. So we only need to update dp[amount] with itself. Then, dp[amount] = min(dp[amount], dp[amount - coins[i]] + 1).

  2. Coin Change II

    1. The idea is same as Coin Change I. Let dp[i][amount] to be the number of combinations of using from 0 to i-th coins to makes up to amount. So, dp[i][amount] = dp[i - 1][amount](not use i-th coin) + dp[i][amount - coins[i]](use i-th coin).

    2. To decrease the space complexity, we can make the dp[i][amount] to be dp[amount]. So, dp[amount] = dp[amount] + dp[amount - coins[i]].

Code

  1. problem 1(version of larger space complexity) 
    class Solution {
 public int coinChange(int[] coins, int amount) {
     int N = coins.length;
     if(N == 0) {
         if(amount == 0) return 0;
         else return -1;
     }
     Arrays.sort(coins);
     int[][] dp = new int[N][amount + 1];
     for(int i = 0; i < N; i ++){
         dp[i][0] = 0;
     }
     for(int i = 1; i <= amount; i ++){
         if(i % coins[0] == 0){
             dp[0][i] = i / coins[0];
         } else{
             dp[0][i] = Integer.MAX_VALUE;
         }
     }
     for(int i = 1; i < N; i ++){
         for(int j = 1; j <= amount; j ++){
             dp[i][j] = dp[i - 1][j];
             if(j >= coins[i] && dp[i][j - coins[i]] < Integer.MAX_VALUE)
                dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i]] + 1);
         }
     }
     return dp[N - 1][amount] == Integer.MAX_VALUE ? -1 : dp[N - 1][amount];
 }
}
  2. problem 1(version of smaller space complexity) 
    class Solution {
 public int coinChange(int[] coins, int amount) {
     int N = coins.length;
     if(N == 0) {
         if(amount == 0) return 0;
         else return -1;
     }
     int[] dp = new int[amount + 1];
     Arrays.fill(dp, Integer.MAX_VALUE);
     dp[0] = 0;
     for(int i = 1; i <= N; i ++){
         for(int j = 1; j <= amount; j ++){
             if(j >= coins[i - 1] && dp[j - coins[i - 1]] < Integer.MAX_VALUE){
                 dp[j] = Math.min(dp[j], 1 + dp[j - coins[i - 1]]);
             }
         }
     }
     return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
 }
}
  3. problem 2(version of larger space complexity) 
    class Solution {
 public int change(int amount, int[] coins) {
     int N = coins.length;
     if(amount == 0){
         return 1;
     }
     if(N == 0){
         return 0;
     }
     int[][] dp = new int[N + 1][amount + 1];
     for(int i = 0; i <= N; i ++){
         dp[i][0] = 1;
     }
     for(int i = 1; i <= N; i ++){
         for(int j = 1; j <= amount; j ++){
             dp[i][j] = dp[i - 1][j];
             if(j >= coins[i - 1]){
                 dp[i][j] += dp[i][j - coins[i - 1]];
             }
         }
     }
     return dp[N][amount];
 }
}
  4. problem 2(version of smaller space complexity) 
    class Solution {
 public int change(int amount, int[] coins) {
     int N = coins.length;
     if(amount == 0){
         return 1;
     }
     if(N == 0){
         return 0;
     }
     int[] dp = new int[amount + 1];
     dp[0] = 1;
     for(int i = 1; i <= N; i ++){
         for(int j = 1; j <= amount; j ++){
             if(j >= coins[i - 1]){
                 dp[j] += dp[j - coins[i - 1]];
             }
         }
     }
     return dp[amount];
 }
}