518. Coin Change 2

[Tcdian]

518. Coin Change 2

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

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

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• 硬币种类不超过 500 种
• 结果符合 32 位符号整数

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    if (coins.length === 0) {
        return amount === 0 ? 1 : 0;
    }
    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] = 1;
            } else if (i === 0) {
                dp[i][j] = j >= coins[i] ? dp[i][j - coins[i]] : 0;
            } else {
                dp[i][j] = j >= coins[i] ? dp[i - 1][j] + dp[i][j - coins[i]] : dp[i - 1][j]
            }
        }
    }
    return dp[coins.length - 1][amount];
};

• TypeScript Solution

function change(amount: number, coins: number[]): number {
    if (coins.length === 0) {
        return amount === 0 ? 1 : 0;
    }
    const dp: number[][] = 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] = 1;
            } else if (i === 0) {
                dp[i][j] = j >= coins[i] ? dp[i][j - coins[i]] : 0;
            } else {
                dp[i][j] = j >= coins[i] ? dp[i - 1][j] + dp[i][j - coins[i]] : dp[i - 1][j]
            }
        }
    }
    return dp[coins.length - 1][amount];
}