322.零钱兑换.md

322.零钱兑换

解题思路

贪心法

乍一看，这题用贪心法似乎比较合适。而实际上，贪心法是适用于一定范围内都有解的情况，而这里，在不确定输入的情况下，有很大概率，可能存在不能组合的情况，进行了贪心法最坏的情况，暴露出贪心法的缺点，因此，这里不适合贪心法。

动态规划

存在任意项 n, 它的前一项的次数都会是 n 减去一次组合对应的次数 + 1，即：

f(n) = min(f(n - coin[0]), f(n - coin[1]), ..., f(n - coin[n])) + 1

function coinChange(coins: number[], amount: number): number {
    const max = amount + 1
    const dp = new Array(max).fill(max)
    dp[0] = 0
    for (let i = 1; i < max; i++) {
        for(let j = 0; l < coins.length; j++) {
            if (i > coins[j]) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount]
}