Coin Change 2

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

 

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

 

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

Solution

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    const dp = Array(coins.length + 1)
        .fill(null)
        .map(() => Array(amount + 1).fill(0));

    for (let i = 0; i <= coins.length; i++) {
        dp[i][0] = 1;
    }

    for (let i = 1; i <= coins.length; i++) {
        for (let j = 1; j <= amount; j++) {
            dp[i][j] += dp[i - 1][j];
            if (coins[i - 1] <= j) {
                dp[i][j] += dp[i][j - coins[i - 1]];
            }
        }
    }
    return dp[coins.length][amount];
};

We will implement a DP solution. Let dp[i][j] be the number of possible combinations that add up to j amount of money using coins coins[0:i].

• For the base case:
  • If i = 0, then dp[0][j] = 0 since there are 0 ways to add up to any amount j > 0 using the empty set coins[0:0].
  • If j = 0, then dp[i][0] = 1 since we default it to there being 1 way to add up to 0 (ie. using the empty set).
• For the recursive case, the number of possible combinations is the number of combinations not including the current value coins[i - 1] plus the the total number of combinations that sums up to j - coins[i - 1] using the current available coins coins[0:i + 1] (ie. by adding the current value coins[i - 1] to each of the combinations that sum up to j - coins[i - 1], the new combinations sum up to j).

Optimization

We can optimize the above solution to use O(amount) space as follows:

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    const dp = Array(amount + 1).fill(0);
    dp[0] = 1;

    for (const coin of coins) {
        for (let i = 1; i <= amount; i++) {
            if (coin <= i) {
                dp[i] += dp[i - coin];
            }
        }
    }
    return dp[amount];
};

Notice that from the 2D DP solution, we fill in dp from left to right (row by row), where the next value of the row is only dependent on the direct previous value of the same row and the (not necessarily direct) previous value of the current col. Thus, the direct previous value of each row needs to be stored in dp; and since dp is evaluated col by col, the lower indexed values in dp are all relative to the current col. Hence we can reduce dp down to a 1D array of size amount + 1.

Question

Does above solution still work even if we swap the order of the two loops?

Answer

This destroys the property that one col is evaluated completely before moving on to the next (ie. lose previous value of the current col as we now only have the final previous col values of dp when evaluating the next row). Thus, for this problem, the solution will no longer work.