322.Coin Change

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[1]
0
[2]
3
[5]
5
[1,2,5]
4
[1,2,5]
11
[2,5,10,1]
27
[186,419,83,408]
6249
[156,265,40,280]   // TLE
9109

Solution 1: TLE

DP.

  1. Base case: dp[0] = 0
  2. Induction rule: dp[i] = min(dp[j] + 1) where j < i;

Time: O(n^3)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for(int i = 1; i <= amount; i++) {
      for (int j = 0; j < i; j++) {
        for (int value: coins) {
          if (value == i - j && dp[j] != Integer.MAX_VALUE) {
            dp[i] = Math.min(dp[i], dp[j] + 1);
          }
        }
      }
    }
    return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];
}

Solution 2: accepted 27ms

Dp.
Instead of check every value in (1, i), we only check the possible coin value, which is a much smaller range.

Time: O(n^2)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    Arrays.sort(coins);
    dp[0] = 0;
    for(int i = 1; i <= amount; i++) {
      for (int j = 0; j < coins.length; j++) {
        if (coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE) {
          dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        }
      }
    }
    return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];
}