Coin Change II

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

这一题正是Backpack IV，也就是完全背包问题，求填满背包的组合（唯一的排列，即相同的元素组合只算一种）的数目。

但是区别于Combination Sum IV，那一题名字叫combination，实际是求permutation的种类，因此包含了相同元素组合但不同排列的情况。

内外循环的顺序问题：

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