# Coin Change 2 （完全背包问题）

Medium

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

``````Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
``````

Example 2:

``````Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
``````

Example 3:

``````Input: amount = 10, coins = [10]
Output: 1
``````

Note:

You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

## Solution && Analysis

Why the outer loop is the coins, not the amount?

The reason behind that is that as you mentioned, the problem is to find the total number of combinations, not the permutations.
If the outer loop is the amount, then the same combination will be counted multiple times because they can come in in different orders.
By letting the coins to be the outer loops, one assures that for any valid combination, the order of each coin will always be the same as their order in coins, so there can be no duplicates.

### Approach - Naive Dynamic Programming

State
`f[i][j]` - the number of combinations to make up amount `j` with the first `i` types of coins.

Induction Rule

`f[i][j] = sum(f[i - 1][j - k * coins[i - 1]]), 0 <= k <= j / coins[i - 1]`

Base Case
`f[0][0] = 1`
`f[0][1,...,m] = 0`

Code -- O(n * m^2) time and O(nm) extra space

``````class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] f = new int[n + 1][amount + 1];

f[0][0] = 1;

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= amount; j++) {
f[i][j] = 0;
for (int k = 0; k * coins[i - 1] <= j; k++) {
f[i][j] += f[i - 1][j - k * coins[i - 1]];
}
}
}

return f[n][amount];
}
}
``````

Another Implementation

``````class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];

dp[0][0] = 1;

for (int i = 1; i <= n; i++) {
dp[i][0] = 1;
for (int j = 1; j <= amount; j++) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k * coins[i - 1] <= j; k++) {
dp[i][j] += dp[i - 1][j - k * coins[i - 1]];
}
}
}

return dp[n][amount];
}
}
``````

### Approach - Time Complexity Optimized Dynamic Programming

State
`f[i][j]` - the number of combinations to make up amount `j` with the first `i` types of coins.

Induction Rule

`f[i][j] = sum(f[i - 1][j - k * coins[i - 1]]), 0 <= k <= j / coins[i - 1]`

For amount `j`:

``````f[i][j] =
f[i - 1][j] +
f[i - 1][j - coins[i - 1]] +
f[i - 1][j - coins[i - 1] * 2] +
f[i - 1][j - coins[i - 1] * 3] +
...
``````

For amount `j - coins[i - 1]`:

``````f[i][j - coins[i - 1] =
f[i - 1][j - coins[i - 1]] +
f[i - 1][j - coins[i - 1] * 2] +
f[i - 1][j - coins[i - 1] * 3] +
...
``````

So, we can optimize the calculation of `f[i][j]` using `f[i][j - coins[i - 1]]`:

``````f[i][j] =
f[i - 1][j] +
f[i - 1][j - coins[i - 1]] +
f[i - 1][j - coins[i - 1] * 2] +
f[i - 1][j - coins[i - 1] * 3] +
...

= f[i - 1][j] + f[i][j - coins[i - 1]
``````

Base Case
`f[0][0] = 1`
`f[0][1,...,m] = 0`

Code -- O(n * m) time and O(nm) extra space

``````class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] f = new int[n + 1][amount + 1];

f[0][0] = 1;

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= amount; j++) {
if (j >= coins[i - 1]) {
f[i][j] = f[i - 1][j] + f[i][j - coins[i - 1]];
} else {
f[i][j] = f[i - 1][j];
}
}
}

return f[n][amount];
}
}
``````

### Approach - Space Complexity Optimized Dynamic Programming

``````for (i = ...) {
for (j = ...) {
// Invariant: g[k] == f[i][k]      if k < j, or
//            g[k] == f[i - 1][k]  if k >= j
g[j] = g[j] + g[j - coins[i - 1]];
}
}
``````

Code -- O(nm) time and O(m) extra space

``````class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] g = new int[amount + 1];

g[0] = 1;

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= amount; j++) {
if (j >= coins[i - 1]) {
g[j] += g[j - coins[i - 1]];
}
}
}

return g[amount];
}
}
``````

## Reference

Laioffer - Coin Change II