参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

518.零钱兑换II

力扣题目链接

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 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

注意，你可以假设：

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

算法公开课

《代码随想录》算法视频公开课：装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II，相信结合视频再看本篇题解，更有助于大家对本题的理解。

二维dp讲解

如果大家认真做完：分割等和子集，最后一块石头的重量II 和目标和

应该会知道类似这种题目：给出一个总数，一些物品，问能否凑成这个总数。

这是典型的背包问题！

本题求的是装满这个背包的物品组合数是多少。

因为每一种面额的硬币有无限个，所以这是完全背包。

对完全背包还不了解的同学，可以看这篇：完全背包理论基础

但本题和纯完全背包不一样，纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数！

注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？

例如示例一：

5 = 2 + 2 + 1

5 = 2 + 1 + 2

这是一种组合，都是 2 2 1。

如果问的是排列数，那么上面就是两种排列了。

组合不强调元素之间的顺序，排列强调元素之间的顺序。其实这一点我们在讲解回溯算法专题的时候就讲过。

那我为什么要介绍这些呢，因为这和下文讲解遍历顺序息息相关!

本题其实与我们讲过 494. 目标和十分类似。

494. 目标和求的是装满背包有多少种方法，而本题是求装满背包有多少种组合。

这有啥区别？

求装满背包有几种方法其实就是求组合数。不过 494. 目标和是 01背包，即每一类物品只有一个。

以下动规五部曲：

1、确定dp数组以及下标的含义

定义二维dp数值 dp[i][j]：使用下标为[0, i]的coins[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种组合方法。

很多录友也会疑惑，凭什么上来就定义 dp数组，思考过程是什么样的，这个思考过程我在 01背包理论基础（二维数组）中的 “确定dp数组以及下标的含义” 有详细讲解。

（强烈建议按照代码随想录的顺序学习，否则可能看不懂我的讲解）

2、确定递推公式

注意：这里的公式推导，与之前讲解过的 494. 目标和、完全背包理论基础有极大重复，所以我不在重复讲解原理，而是只讲解区别。

我们再回顾一下，01背包理论基础，中二维DP数组的递推公式为：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

在完全背包理论基础详细讲解了完全背包二维DP数组的递推公式为：

dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

看去完全背包和 01背包的差别在哪里？

在于01背包是 dp[i - 1][j - weight[i]] + value[i] ，完全背包是 dp[i][j - weight[i]] + value[i])

主要原因就是完全背包单类物品有无限个。

具体原因我在完全背包理论基础（二维）的「确定递推公式」有详细讲解，如果大家忘了，再回顾一下。

我上面有说过，本题和 494. 目标和是一样的，唯一区别就是 494. 目标和是 01背包，本题是完全背包。

在494. 目标和中详解讲解了装满背包有几种方法，二维DP数组的递推公式： dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]

所以本题递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]] ，区别依然是 dp[i - 1][j - nums[i]] 和 dp[i][j - nums[i]]

这个 ‘所以’ 我省略了很多推导的内容，因为这些内容在 494. 目标和和完全背包理论基础都详细讲过。

这里不再重复讲解。

大家主要疑惑点

1、 dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]] 这个递归公式框架怎么来的，在 494. 目标和有详细讲解。

2、为什么是 dp[i][j - nums[i]] 而不是 dp[i - 1][j - nums[i]] ，在完全背包理论基础（二维）有详细讲解

3. dp数组如何初始化

那么二维数组的最上行和最左列一定要初始化，这是递推公式推导的基础，如图红色部分：

这里首先要关注的就是 dp[0][0] 应该是多少？

背包空间为0，装满「物品0」的组合数有多少呢？

应该是 0 个，但如果「物品0」的数值就是0呢？岂不是可以有无限个0 组合和为0！

题目描述中说了1 <= coins.length <= 300 ，所以不用考虑物品数值为0的情况。

那么最上行dp[0][j] 如何初始化呢？

dp[0][j]的含义：用「物品0」（即coins[0]）装满背包容量为j的背包，有几种组合方法。（如果看不懂dp数组的含义，建议先学习494. 目标和）

如果 j 可以整除物品0，那么装满背包就有1种组合方法。

初始化代码：

for (int j = 0; j <= bagSize; j++) {
    if (j % coins[0] == 0) dp[0][j] = 1;
}

最左列如何初始化呢？

dp[i][0] 的含义：用物品i（即coins[i]）装满容量为0的背包有几种组合方法。

都有一种方法，即不装。

所以 dp[i][0] 都初始化为1

4. 确定遍历顺序

二维DP数组的完全背包的两个for循环先后顺序是无所谓的。

先遍历背包，还是先遍历物品都是可以的。

原理和 01背包理论基础（二维数组）中的「遍历顺序」是一样的，都是因为两个for循环的先后顺序不影响递推公式所需要的数值。

具体分析过程看 01背包理论基础（二维数组）中的「遍历顺序」

5. 打印DP数组

以amount为5，coins为：[2,3,5] 为例：

dp数组应该是这样的：

1 0 1 0 1 0
1 0 1 1 1 1
1 0 1 1 1 2

代码实现：

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

        vector<vector<uint64_t>> dp(coins.size(), vector<uint64_t>(bagSize + 1, 0));

        // 初始化最上行
        for (int j = 0; j <= bagSize; j++) {
            if (j % coins[0] == 0) dp[0][j] = 1;
        }
        // 初始化最左列
        for (int i = 0; i < coins.size(); i++) {
            dp[i][0] = 1;
        }
        // 以下遍历顺序行列可以颠倒
        for (int i = 1; i < coins.size(); i++) { // 行，遍历物品
            for (int j = 0; j <= bagSize; j++) { // 列，遍历背包
                if (coins[i] > j) dp[i][j] = dp[i - 1][j]; 
                else dp[i][j] = dp[i - 1][j] +  dp[i][j - coins[i]];
            }
        }
        return dp[coins.size() - 1][bagSize];
    }
};

一维dp讲解

1、确定dp数组以及下标的含义

dp[j]：凑成总金额j的货币组合数为dp[j]

2、确定递推公式

本题二维dp 递推公式： dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]

压缩成一维：dp[j] += dp[j - coins[i]]

这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在这篇494. 目标和中就讲解了，求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]]

3. dp数组如何初始化

装满背包容量为0 的方法是1，即不放任何物品，dp[0] = 1

4. 确定遍历顺序

本题中我们是外层for循环遍历物品（钱币），内层for遍历背包（金钱总额），还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？

我在完全背包（一维DP）中讲解了完全背包的两个for循环的先后顺序都是可以的。

但本题就不行了！

因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！

而本题要求凑成总和的组合数，元素之间明确要求没有顺序。

所以纯完全背包是能凑成总和就行，不用管怎么凑的。

本题是求凑出来的方案个数，且每个方案个数是组合数。

那么本题，两个for循环的先后顺序可就有说法了。

我们先来看外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。

代码如下：

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}

假设：coins[0] = 1，coins[1] = 5。

那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。

所以这种遍历顺序中dp[j]里计算的是组合数！

如果把两个for交换顺序，代码如下：

for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数！

可能这里很多同学还不是很理解，建议动手把这两种方案的dp数组数值变化打印出来，对比看一看！（实践出真知）

5. 举例推导dp数组

输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：

最后红色框dp[amount]为最终结果。

以上分析完毕，C++代码如下：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<uint64_t> dp(amount + 1, 0); // 防止相加数据超int
        dp[0] = 1; // 只有一种方式达到0
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount]; // 返回组合数
    }
};

C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。

时间复杂度: O(mn)，其中 m 是amount，n 是 coins 的长度
空间复杂度: O(m)

为了防止相加的数据超int 也可以这么写：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1; // 只有一种方式达到0
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                if (dp[j] < INT_MAX - dp[j - coins[i]]) { //防止相加数据超int
                    dp[j] += dp[j - coins[i]];
                }
            }
        }
        return dp[amount]; // 返回组合数
    }
};

总结

本题我们从二维分析到一维。

大家在刚开始学习的时候，从二维开始学习容易理解。

之后，推荐大家直接掌握一维的写法，熟练后更容易写出来。

本题中，二维dp主要是就要想清楚和我们之前讲解的 01背包理论基础、494. 目标和、完全背包理论基础联系与区别。

这也是代码随想录安排刷题顺序的精髓所在。

本题的一维dp中，难点在于理解便利顺序。

在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

可能说到排列数录友们已经有点懵了，后面我还会安排求排列数的题目，到时候在对比一下，大家就会发现神奇所在！

其他语言版本

Java：

class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

// 二维dp数组版本，方便理解
class Solution {
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length][amount+1];

        // 初始化边界值
        for(int i = 0; i < coins.length; i++){
            // 第一列的初始值为1
            dp[i][0] = 1;
        }
        for(int j = coins[0]; j <= amount; j++){
            // 初始化第一行
            dp[0][j] += dp[0][j-coins[0]];
        }
        
        for(int i = 1; i < coins.length; i++){
            for(int j = 1; j <= amount; j++){
                if(j < coins[i]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j];
            }
        }

        return dp[coins.length-1][amount];
    }
}

Python：

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0]*(amount + 1)
        dp[0] = 1
        # 遍历物品
        for i in range(len(coins)):
            # 遍历背包
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        return dp[amount]

Go：

一维dp

func change(amount int, coins []int) int {
	// 定义dp数组
	dp := make([]int, amount+1)
	// 初始化,0大小的背包, 当然是不装任何东西了, 就是1种方法
	dp[0]  = 1
	// 遍历顺序
	// 遍历物品
	for i := 0 ;i < len(coins);i++ {
		// 遍历背包
		for j:= coins[i] ; j <= amount ;j++ {
			// 推导公式
			dp[j] += dp[j-coins[i]]
		}
	}
	return dp[amount]
}

二维dp

func change(amount int, coins []int) int {
    dp := make([][]int, len(coins))
    for i := range dp {
        dp[i] = make([]int, amount + 1)
        dp[i][0] = 1
    }
    for j := coins[0]; j <= amount; j++ {
        dp[0][j] += dp[0][j-coins[0]]
    }
    for i := 1; i < len(coins); i++ {
        for j := 1; j <= amount; j++ {
            if j < coins[i] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j]
            }
        }
    }
    return dp[len(coins)-1][amount]
}

Rust:

impl Solution {
    pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
        let amount = amount as usize;
        let mut dp = vec![0; amount + 1];
        dp[0] = 1;
        for coin in coins {
            for j in coin as usize..=amount {
                dp[j] += dp[j - coin as usize];
            }
        }
        dp[amount]
    }
}

JavaScript：

const change = (amount, coins) => {
    let dp = Array(amount + 1).fill(0);
    dp[0] = 1;

    for(let i =0; i < coins.length; i++) {
        for(let j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }

    return dp[amount];
}

TypeScript：

function change(amount: number, coins: number[]): number {
    const dp: number[] = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (let i = 0, length = coins.length; i < length; i++) {
        for (let j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
};

Scala:

object Solution {
  def change(amount: Int, coins: Array[Int]): Int = {
    var dp = new Array[Int](amount + 1)
    dp(0) = 1
    for (i <- 0 until coins.length) {
      for (j <- coins(i) to amount) {
        dp(j) += dp(j - coins(i))
      }
    }
    dp(amount)
  }
}

C

int change(int amount, int* coins, int coinsSize) {
    int dp[amount + 1];
    memset(dp, 0, sizeof (dp));
    dp[0] = 1;
    // 遍历物品
    for(int i = 0; i < coinsSize; i++){
        // 遍历背包
        for(int j = coins[i]; j <= amount; j++){
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

C#

public class Solution
{
    public int Change(int amount, int[] coins)
    {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < coins.Length; i++)
        {
            for (int j = coins[i]; j <= amount; j++)
            {
                if (j >= coins[i])
                    dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

回归本题，动规五步曲来分析如下：

确定dp数组以及下标的含义

dp[j]：凑成总金额j的货币组合数为dp[j]

确定递推公式

dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。

所以递推公式：dp[j] += dp[j - coins[i]];

这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在这篇494. 目标和中就讲解了，求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];

dp数组如何初始化

首先dp[0]一定要为1，dp[0] = 1是递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。

那么 dp[0] = 1 有没有含义，其实既可以说凑成总金额0的货币组合数为1，也可以说凑成总金额0的货币组合数为0，好像都没有毛病。

但题目描述中，也没明确说 amount = 0 的情况，结果应该是多少。

这里我认为题目描述还是要说明一下，因为后台测试数据是默认，amount = 0 的情况，组合数为1的。

下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]

dp[0]=1还说明了一种情况：如果正好选了coins[i]后，也就是j-coins[i] == 0的情况表示这个硬币刚好能选，此时dp[0]为1表示只选coins[i]存在这样的一种选法。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0518.零钱兑换II.md

0518.零钱兑换II.md

518.零钱兑换II

算法公开课

二维dp讲解

1、确定dp数组以及下标的含义

2、确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 打印DP数组

代码实现：

一维dp讲解

1、确定dp数组以及下标的含义

2、确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

总结

其他语言版本

Java：

Python：

Go：

Rust:

JavaScript：

TypeScript：

Scala:

C

C#

Files

0518.零钱兑换II.md

Latest commit

History

0518.零钱兑换II.md

File metadata and controls

518.零钱兑换II

算法公开课

二维dp讲解

1、确定dp数组以及下标的含义

2、确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 打印DP数组

代码实现：

一维dp讲解

1、确定dp数组以及下标的含义

2、确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

总结

其他语言版本

Java：

Python：

Go：

Rust:

JavaScript：

TypeScript：

Scala:

C

C#