322. 零钱兑换

Origin: LeetCode 322

题目描述

给定不同面额的硬币 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币个数。如果无法凑出，返回 -1。每种硬币可无限次使用。

示例

Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Input: coins = [2], amount = 3 Output: -1

Input: coins = [1], amount = 0 Output: 0

约束

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10

关键信息

• 完全背包，硬币无限次使用
• dp[i] = min(dp[i], dp[i - coin] + 1)
• 和 HackerRank 第 37 题、LeetCode 第 279 题完全一样的框架
• 凑不出返回 -1（Infinity 判断）

Resolution

我的解法

function coinChange(coins: number[], amount: number): number {
    // dp[i] = min(dp[i], dp[i - coin] + 1)
    const dp = Array.from({ length: amount + 1 }, () => Infinity)
    dp[0] = 0
    for (let i = 1; i <= amount; i++) {
        let min = dp[i]
        for (const coin of coins) {
            if (i >= coin) {
                min = Math.min(min, dp[i - coin] + 1)
            }
        }
        dp[i] = min
    }
    return dp[amount] === Infinity ? -1 : dp[amount]
}

解题思路

完全背包 / 硬币找零。和 HackerRank 第 37 题、LeetCode 第 279 题完全一样的框架。

• dp[i] = 凑齐金额 i 所需的最少硬币数
• dp[0] = 0，其他初始化 Infinity
• 对每个金额 i，遍历所有硬币，dp[i] = min(dp[i], dp[i - coin] + 1)
• i >= coin 防越界，最后 Infinity 返回 -1

复杂度

• 时间：O(n × m)，n 是 amount，m 是 coins 长度
• 空间：O(n)