Coin Change

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 fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

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

 

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

 

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Solution

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

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

    for (let i = 1; i <= amount; i++) {
        for (let j = 1; j <= coins.length; j++) {
            if (coins[j - 1] > i) { // coin denomination > amount
                dp[i][j] = dp[i][j - 1];
            } else { // coin denomination <= amount
                dp[i][j] = Math.min(dp[i][j - 1], 1 + dp[i - coins[j - 1]][j])
            }
        }
    }

    return dp[amount][coins.length] === Infinity ? -1 : dp[amount][coins.length];
};

We will implement a DP solution. Let dp[i][j] be the min number of coins from coins[0:j] to make up i amount of money.

• For the base case:
  • If i = 0, then dp[0][j] = Infinity since using coins[0:0] (ie. no coins) cannot make up any amount of money (note we use Infinity to represent impossible).
  • If j = 0, then dp[i][0] = 0 since 0 amount of money can be made up using 0 coins.
• For the recursive case, if the current coin coin[j - 1] has a greater denomination value than the amount we are trying to make, there's no way to use this coin, so we use the min number of coins without including this coin (ie. dp[i][j - 1]). Otherwise, we take the min of either not including the current coin (ie. dp[i][j - 1]) or using the current coin (ie. 1 + dp[i - coins[j - 1]][j]).

Optimization

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

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

    for (const coin of coins) {
        for (let i = 1; i <= amount; i++) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], 1 + dp[i - coin])
            }
        }
    }
    return dp[amount] === Infinity ? -1 : 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). That said, in this problem, the ordering does not actually matter (see explanation below), and so the solution will still work.

First, observe that each row of dp is non-decreasing due to the min operator, so taking the min of the smallest value before is the same as later (eg. min(min(9, 10), 1) = (min(9, 1), 10) = 1, but the intermediate value of min(9, 10) != min(9, 1)).

In our 2D version, eventually we will be taking the min of the previous value in the row and the last col value when our loop reaches j = coins.length. Thus, it won't effect the final solution even if we use 1 + dp[i - coins[j - 1]][coins.length] instead of 1 + dp[i - coins[j - 1]][j] (since the last value in any row of dp is always the smallest value of that entire row). That said, all values of dp that are not in the last col will be messed up (correct last col value implies correct final result).