322. 零钱兑换

[Geekhyt]

原题链接

题目仅要求出最少硬币数量，无须考虑硬币的组合和排列，所以不用考虑两个 for 循环的内外顺序。

状态定义

dp[i]：凑足总额为 i 所需钱币的最少个数为 dp[i]

状态转移方程

dp[i] = min(dp[j - coins[j]] + 1, dp[i])

理解

不考虑第 j 个硬币时， 硬币数为 dp[i]

考虑第 j 个硬币时，硬币数为 dp[i - coins[j]] + 1

初始化

凑足总金额为 0 所需钱币的个数是 0，所以 dp[0] = 0

下标非 0 元素应该为最大值： Number.MAX_VALUE

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

• 时间复杂度: O(len(coins) * amount)
• 空间复杂度: O(amount)