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

动态规划

一维数组

这段代码是在解决一个称为"零钱兑换 II"的动态规划问题。具体来说，它计算了使用一个无限数量的不同面额硬币凑成某个总金额的所有可能组合的数目。代码使用了C++语言。下面是对这段代码的逐行解释：

// 定义一个Solution类
class Solution {
public:// 定义并实现一个名为change的公共成员函数int change(int amount, vector<int>& coins) {// dp定义了一个整型向量(dp数组)，大小为amount + 1，所有值初始化为0vector<int>dp(amount+1, 0);// 将dp数组的第一项设置为1，这表示金额为0的话有1种方式（就是不用任何硬币）dp[0] = 1;// 遍历coins数组，i为索引，从0开始到coins.size() - 1for(int i = 0; i < coins.size(); i++)// 从当前硬币面额coins[i]开始，直到总金额for(int j = coins[i]; j <= amount; j++)// 更新dp[j]的值：dp[j] = dp[j] + dp[j - coins[i]]// 这表示加上用当前的硬币面额coins[i]凑出金额j的新组合数dp[j] += dp[j - coins[i]];// 最后返回dp数组的最后一项，即凑成总金额amount的组合数return dp[amount];}
};

解释一下这个动态规划的核心思想：

• dp数组的定义：dp[i]表示凑成总金额为i的硬币组合数。
• 初始化：由于凑成总金额为0的方式只有一种，就是不使用任何硬币，所以初始化dp[0] = 1。
• 外层循环：遍历每一种硬币。
• 内层循环：对于每一种硬币，更新金额从硬币面额到总金额的所有dp值。
• 状态转移方程：dp[j] += dp[j - coins[i]]的含义是，对于每个金额j，考虑当前的硬币面额coins[i]，如果我们知道了组成金额j - coins[i]的组合数（即dp[j - coins[i]]），那么就可以通过添加一个coins[i]硬币来得到金额j的一个新的组合。所以，我们要将组成金额j - coins[i]的所有组合数加到dp[j]上。

这个算法的时间复杂度是O(n*m)，n是金额amount，m是硬币种类数。空间复杂度是O(n)，因为我们使用了一个n + 1大小的dp数组。

为什么不能交换两个for循环的顺序？

在这个特定的动态规划问题中，两个for循环的顺序决定了硬币组合数是如何被计算的，特别是它们影响了状态转移方程的更新方式。如果交换了循环的顺序，将会改变动态规划算法的整个逻辑。

原始顺序（先遍历硬币，然后遍历金额）的循环确保了以下几点：

1. 组合性：当计算dp[j]时（即凑成金额j的方法数），算法仅考虑使用当前硬币和之前考虑过的硬币的组合。这意味着，对于每个硬币，你都是在累积之前的结果上增加新的可能性。

2. 无重复：这个顺序确保了在计算组合数时，相同面额的硬币不会被重复计算。即我们不会得到多个考虑顺序不同但实际上相同的硬币组合。

3. 有序：由于每次循环都是在之前硬币的基础上加上新硬币，因此所有的组合都是以一种有序的方式生成的。

如果交换了for循环的顺序，算法将会改变上述逻辑，导致以下问题：

• 每次计算dp[j]时，都会考虑所有硬币，这意味着同一金额会被重复计算多次，从而破坏了动态规划的基本原则。
• 容易出现重复组合，因为对于每个金额，你都在尝试所有的硬币，无法保证硬币使用的唯一顺序，从而可能导致重复的组合方式被计数。
• 缺乏顺序性，因为你在每个金额的计算中都包含了所有的硬币，这样就会有多种硬币组合顺序产生相同的金额，这些都被错误地算作不同的组合。

因此，保持原始的循环顺序对于解决这个动态规划问题是很重要的，它确保了算法的正确性和效率。

二维数组

这段代码是解决"零钱兑换 II"问题的动态规划解法。下面是对代码的详细注释：

class Solution {
public:int change(int amount, vector<int>& coins) {// 初始化动态规划表格。行数为coins.size()+1，代表0到coins.size个硬币，列数为amount+1，代表0到amount的金额。// dp[i][j]表示使用前i种硬币凑成金额j的方法数。vector<vector<int>> dp(coins.size()+1,vector<int>(amount+1,0));// base case：当金额为0时，即j=0，不使用任何硬币就能凑齐，因此方法数为1。dp[0][0]=1;// 遍历所有的硬币种类for(int i=1;i<=coins.size();i++){// 对于每一种硬币，遍历所有可能的金额for(int j=0;j<=amount;j++){// dp[i][j]首先继承dp[i-1][j]的值，即不使用第i种硬币时凑成金额j的方法数。dp[i][j]=dp[i-1][j];// 如果当前金额j大于等于当前考虑的硬币面额coins[i-1]，// 则可以考虑使用这种硬币。此时的方法数为dp[i][j-coins[i-1]]，// 加上这种硬币之前的方法数，因为dp[i][j-coins[i-1]]已经计算了使用前i种硬币凑成金额j-coins[i-1]的方法数。if(j>=coins[i-1])dp[i][j]+=dp[i][j-coins[i-1]];}}// 返回使用所有硬币凑成总金额amount的方法数。return dp[coins.size()][amount];}
};

核心思想：

• 动态规划表dp的大小为(coins.size()+1) * (amount+1)，dp[i][j]表示使用前i种硬币（其中硬币种类从0开始编号）凑成金额j的方法数。
• 初始化dp[0][0]=1表示不使用任何硬币凑成金额0的方法有1种。
• 外层循环遍历硬币种类，内层循环遍历可能的金额。
• 对于每一种硬币coins[i-1]和每一个金额j，如果j大于等于当前硬币的面额，我们有两个选择：不使用当前的硬币（继承dp[i-1][j]的值），或者使用当前的硬币（dp[i][j-coins[i-1]]加上当前硬币的数量）。
• 最终，dp[coins.size()][amount]是使用所有硬币凑成金额amount的方法数。