跳转至

322. 零钱兑换

力扣链接(中等)：https://leetcode.cn/problems/coin-change

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

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

Text Only
1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

Text Only
1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

Text Only
1
2
输入：coins = [1], amount = 0
输出：0

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

个人题解

建议完成 494. 目标和 、416. 分割等和子集 和 518. 零钱兑换 II 后再完成本题。

  1. dp[j] 表示凑齐总额 j 至少需要 dp[j] 枚硬币；
  2. 递推公式显然为 dp[j] = min(dp[j], dp[j - coins[i]] + 1)；
  3. 凑齐 0 元需要 0 枚硬币，初始化 dp[0] = 0；
  4. 本题本题不强调排列还是组合，for 循环层次顺序无所谓；本题为完全背包问题，滚动数组从前向后遍历；
  5. 手动推导 dp 数组无误。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 每种硬币的数量是无限的，完全背包问题
        // 凑成总金额所需的最少的硬币个数，dp[j] 要取最小的
        // 本题不强调排列还是组合，求最小硬币数量即可
        const int N = 10010;
        int dp[N];
        // 因为要找最小值，所以这里应该初始化为最大值，这样后续才会被覆盖
        fill(dp, dp + N, INT_MAX);

        // 需要 0 个硬币凑出金额 0
        dp[0] = 0;

        for(int i = 0; i < coins.size(); i++) {
            for(int j = coins[i]; j <= amount; j++) {
                // 注意排除 dp[j - coins[i]] == INT_MAX 防止越界
                if(dp[j - coins[i]] != INT_MAX) 
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        // for(int j = 0; j <= amount; j++) {
        //     for(int i = 0; i < coins.size(); i++) {
        //         // 注意排除 dp[j - coins[i]] == INT_MAX 初始化数据
        //         if(j - coins[i] >= 0 && dp[j - coins[i]] != INT_MAX) 
        //             dp[j] = min(dp[j], dp[j - coins[i]] + 1);
        //     }
        // }

        if(dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};