零钱兑换2.md

零钱兑换2

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 `amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

题解

是取组合总数而不是排列总数，所以保证循环时后面的硬币不再和前面的硬币组合。

所以 coins 在外层的循环。

dp[i] 定义：每一轮 coin 时面额为i的组合数

初始化 dp[i] = 0，特别的有dp[0] = 1，不选取也是一种组合

对于每一轮 coin 而言，如果存在一种硬币组合的金额之和等于 i − coin，则在该硬币组合中增加一个面额为 coin 的硬币，即可得到一种金额之和等于 i 的硬币组合，所以有：

dp[i] = dp[i] + dp[i - coin]

/**
 * @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 item of coins) {
        for (let i = item; i < amount + 1; i++) {
            dp[i] = dp[i] + dp[i - item]
        }
    }
    return dp[amount]
};