网站开发怎样,郑州做网站九零后网络,建设局主要负责什么,微信网站建设公司文章目录 518. 零钱兑换 II题目描述动态规划一维数组为什么不能交换两个for循环的顺序#xff1f; 二维数组 518. 零钱兑换 II
题目描述
给你一个整数数组 coins 表示不同面额的硬币#xff0c;另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数… 文章目录 518. 零钱兑换 II题目描述动态规划一维数组为什么不能交换两个for循环的顺序 二维数组 518. 零钱兑换 II
题目描述
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1 输入amount 5, coins [1, 2, 5] 输出4 解释有四种方式可以凑成总金额 55 5221 52111 511111 示例 2 输入amount 3, coins [2] 输出0 解释只用面额 2 的硬币不能凑成总金额 3 。 示例 3 输入amount 10, coins [10] 输出1 提示
1 coins.length 3001 coins[i] 5000coins 中的所有值 互不相同0 amount 5000
动态规划
一维数组
这段代码是在解决一个称为零钱兑换 II的动态规划问题。具体来说它计算了使用一个无限数量的不同面额硬币凑成某个总金额的所有可能组合的数目。代码使用了C语言。下面是对这段代码的逐行解释
// 定义一个Solution类
class Solution {
public:// 定义并实现一个名为change的公共成员函数int change(int amount, vectorint coins) {// dp定义了一个整型向量(dp数组)大小为amount 1所有值初始化为0vectorintdp(amount1, 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是金额amountm是硬币种类数。空间复杂度是O(n)因为我们使用了一个n 1大小的dp数组。
为什么不能交换两个for循环的顺序
在这个特定的动态规划问题中两个for循环的顺序决定了硬币组合数是如何被计算的特别是它们影响了状态转移方程的更新方式。如果交换了循环的顺序将会改变动态规划算法的整个逻辑。
原始顺序先遍历硬币然后遍历金额的循环确保了以下几点 组合性当计算dp[j]时即凑成金额j的方法数算法仅考虑使用当前硬币和之前考虑过的硬币的组合。这意味着对于每个硬币你都是在累积之前的结果上增加新的可能性。 无重复这个顺序确保了在计算组合数时相同面额的硬币不会被重复计算。即我们不会得到多个考虑顺序不同但实际上相同的硬币组合。 有序由于每次循环都是在之前硬币的基础上加上新硬币因此所有的组合都是以一种有序的方式生成的。
如果交换了for循环的顺序算法将会改变上述逻辑导致以下问题
每次计算dp[j]时都会考虑所有硬币这意味着同一金额会被重复计算多次从而破坏了动态规划的基本原则。容易出现重复组合因为对于每个金额你都在尝试所有的硬币无法保证硬币使用的唯一顺序从而可能导致重复的组合方式被计数。缺乏顺序性因为你在每个金额的计算中都包含了所有的硬币这样就会有多种硬币组合顺序产生相同的金额这些都被错误地算作不同的组合。
因此保持原始的循环顺序对于解决这个动态规划问题是很重要的它确保了算法的正确性和效率。
二维数组
这段代码是解决零钱兑换 II问题的动态规划解法。下面是对代码的详细注释
class Solution {
public:int change(int amount, vectorint coins) {// 初始化动态规划表格。行数为coins.size()1代表0到coins.size个硬币列数为amount1代表0到amount的金额。// dp[i][j]表示使用前i种硬币凑成金额j的方法数。vectorvectorint dp(coins.size()1,vectorint(amount1,0));// base case当金额为0时即j0不使用任何硬币就能凑齐因此方法数为1。dp[0][0]1;// 遍历所有的硬币种类for(int i1;icoins.size();i){// 对于每一种硬币遍历所有可能的金额for(int j0;jamount;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(jcoins[i-1])dp[i][j]dp[i][j-coins[i-1]];}}// 返回使用所有硬币凑成总金额amount的方法数。return dp[coins.size()][amount];}
};核心思想
动态规划表dp的大小为(coins.size()1) * (amount1)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的方法数。
