322. Coin Change

[Tcdian]

322. Coin Change

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

Note

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

[Tcdian]

Solution ( DP )

• JavaScript Solution

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

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

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