跳至主要內容

LeetCode 518、零钱兑换II

LeetCode 518、零钱兑换II

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

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

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

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

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2**：**

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

提示：

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

二、题目解析

三、参考代码

1、Java 代码

二维DP

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 零钱兑换II（LeetCode 518）：https://leetcode.cn/problems/coin-change-2/submissions/
class Solution {
    public int change(int amount, int[] coins) {
        // 经典的完全背包问题

        // 二维数组：状态定义:dp[i][j]表示从数组 coins 中前 i 个硬币中选择得到价值为 j 的硬币组合数
        int[][] dp = new int[coins.length + 1][ amount + 1 ];

        // 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
        dp[0][0] = 1;

        // Tips：前 i 个物品表示的是编号从 [ 0 , i - 1] 这些物品，即最后一个物品编号为 i - 1
        // coins 数组的大小就是硬币的个数
        for( int i = 1 ; i <= coins.length ; i++){
            // 遍历背包容量
            for( int j = 0 ; j <= amount ; j++){

                // 背包容量小于当前硬币的值，即背包容量已经不足以拿第 i 个硬币了
                // 第 i 个硬币即下标为 i - 1 的那个硬币
                if( j < coins[i - 1]){

                    // 硬币组合数就是去考虑当前背包容量情况下，从前 i - 1 个物品中选择出的硬币组合数
                    dp[i][j] = dp[i - 1][j];

                // 背包容量足够拿第 i 个物品，那么可拿也可不拿
                // 1、拿了，那么硬币组合数是前 i 个硬币扣除第 i 个硬币的情况下的硬币组合数
                // 2、不拿，那么就是从前 i - 1 个硬币中选择出的硬币组合数
                }else{

                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }

                // System.out.print(dp[i][j] + "");
            }
        //  System.out.println();
        }

        return dp[coins.length][amount];

    }
}

一维****DP

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 零钱兑换II（LeetCode 518）：https://leetcode.cn/problems/coin-change-2/submissions/
class Solution {
    public int change(int amount, int[] coins) {
        // 经典的完全背包问题

        // 二维数组：状态定义:dp[i][j]表示从数组 coins 中前 i 个硬币中选择得到价值为 j 的硬币组合数
        int[] dp = new int[ amount + 1 ];

        // 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
        dp[0] = 1;

        // Tips：前 i 个物品表示的是编号从 [ 0 , i - 1] 这些物品，即最后一个物品编号为 i - 1
        // coins 数组的大小就是硬币的个数
        for( int i = 1 ; i <= coins.length ; i++){
            // 遍历背包容量
            for( int j = 0 ; j <= amount ; j++){

                // 背包容量足够拿第 i 个物品，那么可拿也可不拿
                // 1、拿了，那么硬币组合数是前 i 个硬币扣除第 i 个硬币的情况下的硬币组合数
                // 2、不拿，那么就是从前 i - 1 个硬币中选择出的硬币组合数
                if( j >= coins[i - 1]){
                    // 硬币组合数就是去考虑当前背包容量情况下，从前 i - 1 个物品中选择出的硬币组合数
                    dp[j] = dp[j] + dp[j-coins[i-1]];

                }
            }
        }

        return dp[amount];

    }
}

**2、**C++ 代码

特别注意，LeetCode官方自己出了一个非常大的用例来卡通过率，而且只针对C++会卡。

添加了整数最大值约束版本的代码可以通过所有用例。

但是大家也不用专门去学习，因为不添加约束的写法，在99%的情况下都是可以直接使用的。

二维DP（不加整数约束版本，会有用例溢出，一般不会出现）

class Solution {
public:
    int change(int amount, vector<int>& coins) {

        // 经典的完全背包问题

        // 二维数组：状态定义:dp[i][j]表示从数组 coins 中前 i 个硬币中选择得到价值为 j 的硬币组合数
        int n = coins.size();
        vector<vector<int>>dp(n + 1, vector<int>(amount + 1 , 0));

        // 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
        dp[0][0] = 1;

        // Tips：前 i 个物品表示的是编号从 [ 0 , i - 1] 这些物品，即最后一个物品编号为 i - 1
        // coins 数组的大小就是硬币的个数
        for( int i = 1 ; i <= n ; i++){
            // 遍历背包容量
            for( int j = 0 ; j <= amount ; j++){

                // 背包容量小于当前硬币的值，即背包容量已经不足以拿第 i 个硬币了
                // 第 i 个硬币即下标为 i - 1 的那个硬币
                if( j < coins[i - 1]){

                    // 硬币组合数就是去考虑当前背包容量情况下，从前 i - 1 个物品中选择出的硬币组合数
                    dp[i][j] = dp[i - 1][j];

                // 背包容量足够拿第 i 个物品，那么可拿也可不拿
                // 1、拿了，那么硬币组合数是前 i 个硬币扣除第 i 个硬币的情况下的硬币组合数
                // 2、不拿，那么就是从前 i - 1 个硬币中选择出的硬币组合数
                }else{

                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }

            }

        }

        return dp[n][amount];

    }
};

二维DP（添加约束版本，可以通过所有用例）

#include <vector>
#include <limits>
using namespace std;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 经典的完全背包问题

        int n = coins.size();
        // 二维数组：状态定义: dp[i][j] 表示从数组 coins 中前 i 个硬币中选择得到价值为 j 的硬币组合数
        vector<vector<long long>> dp(n + 1, vector<long long>(amount + 1, 0));

        // 只有当不选取任何硬币时，金额之和为 0，此时只有 1 种硬币组合
        dp[0][0] = 1;

        // 遍历硬币
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                // 如果背包容量不足以拿当前硬币
                if (j < coins[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];

                    // 判断并约束 dp[i][j]，防止超出 int 范围
                    if (dp[i][j] > numeric_limits<int>::max()) {
                        dp[i][j] = numeric_limits<int>::max();
                    }
                }
            }
        }

        // 返回最终金额组合数，限制在 int 范围内
        return dp[n][amount] > numeric_limits<int>::max() ? 0 : static_cast<int>(dp[n][amount]);
    }
};

一维DP（不加整数约束版本，会有用例溢出，一般不会出现）

#include <vector>
using namespace std;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 经典的完全背包问题

        // 一维数组：状态定义 dp[j] 表示组合得到金额 j 的方案数
        vector<int> dp(amount + 1, 0);

        // 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
        dp[0] = 1;

        // 遍历每种硬币
        for (int i = 0; i < coins.size(); i++) {
            // 遍历背包容量，从当前硬币值到总金额
            for (int j = coins[i]; j <= amount; j++) {
                // 如果选择当前硬币coins[i]，组合方案数增加dp[j - coins[i]]
                dp[j] += dp[j - coins[i]];
            }
        }

        // 返回最终能凑成金额 amount 的组合数
        return dp[amount];
    }
};

一维DP（添加约束版本，可以通过所有用例）

#include <vector>
#include <limits>
using namespace std;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        // 使用 long long 类型以避免在中间累加时的溢出问题
        vector<long long> dp(amount + 1, 0);

        // 只有当不选取任何硬币时，金额之和为 0，组合数为 1
        dp[0] = 1;

        // 遍历每种硬币
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
                // 将 dp[j] 的值约束在 int 范围内
                if (dp[j] > numeric_limits<int>::max()) {
                    dp[j] = numeric_limits<int>::max();
                }
            }
        }

        // 返回最终能凑成金额 amount 的组合数，结果约束在 int 范围内
        return dp[amount] > numeric_limits<int>::max() ? 0 : static_cast<int>(dp[amount]);
    }
};

3、Python 代码

二维DP

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        n = len(coins)
        dp = [[0]*(amount+1) for _ in range(n+1)] 

        # 初始化
        dp[0][0] = 1    
        
        # 完全背包
        # 第一层循环：遍历硬币
        for i in range(1, n+1):  

            # 第二层循环：遍历背包
            for j in range(amount+1):   
                # 容量有限，无法选择第i个硬币
                if j < coins[i-1]:     
                    dp[i][j] = dp[i-1][j]
                # 可选择第i个硬币
                else:                  
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
        
        return dp[n][amount]

一维DP

class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        # 经典的完全背包问题

        # 一维数组：状态定义 dp[j] 表示组合得到金额 j 的方案数
        dp = [0] * (amount + 1)

        # 只有当不选取任何硬币时，金额之和才为 0，此时只有 1 种硬币组合
        dp[0] = 1

        # 遍历每种硬币
        for coin in coins:
            # 遍历背包容量，从当前硬币值到总金额
            for j in range(coin, amount + 1):
                # 如果选择当前硬币coin，组合方案数增加dp[j - coin]
                dp[j] += dp[j - coin]

        # 返回最终能凑成金额 amount 的组合数
        return dp[amount]
本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法