dp专题13 零钱兑换II

原创已于 2024-01-17 11:20:04 修改 · 粉丝可见 · 464 阅读 · 7 · 7 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135625365

本题链接： . - 力扣（LeetCode）

题目：

思路：

根据题意，这是一道很裸的背包问题，其中这里是返回背包方案数的。

我们可以直接推出公式：dp[ j ] += dp[ j - coins[ i ] ]

在我之前做的笔记中，写过具体的背包方案数dp公式，参考我之前的详解即可： dp专题10 目标和

最后我们再明确一下题目，题目要求是硬币数量是无限的，说明这是一个完全背包问题。

完全背包问题和 01 背包问题区别在于遍历背包的顺序。

01 背包的背包遍历顺序：逆向。

完全背包的背包遍历顺序：正向。

具体原理是：

背包逆向遍历的时候，物品只能取 1 次.(01 背包)

代码详解：

 
for(int i = 0;i < goods.size();++i)
{
    for(int j = v;j >= goods[i].v;--j)
    {
        dp[j] = max(dp[j],dp[j - goods.v] + goods.w);
    }
}
 
/*

  逆向 的时候，  j == 背包容量(v)   时， 只能取当前的一个 物品 i  
                随后随着 --j   后面  dp[j]  紧随其后  只取一个物品 i       
                所以达到了，只取 一次 的效果
*/

背包正向遍历的时候，物品可以取多次.(完全背包)

代码详解：

 
for(int i = 0;i < goods.size();++i)
{
    for(int j = goods[i].v;j <= v;++j)
    {
        dp[j] = max(dp[j],dp[j - goods.v] + goods.w);
    }
}
 
/*

  正向 的时候，  j == 物品容量(goods.v)   时， 取当前的一个 物品 i  
                随后随着 ++j   后面  dp[j]  紧随其后 取一个物品 i       
                直到达到了 dp[v] ，使得 物品 i 取了多次
*/

所以完全背包问题和 01 背包问题区别在于遍历背包的顺序。

同样的道理，我们结合dp递推的公式 + 背包遍历顺序，就可以解出这道完全背包问题方案数的问题了。

在这里再扩展一下问题，遍历顺序中，先遍历背包还是先遍历物品？

我们再看一下这两种遍历方法的效果：

①先遍历物品再遍历背包

 
for(int i = 0;i < goods.size();++i)    // 遍历物品
{
    for(int j = goods[i].v;j <= v;++j)    // 遍历背包
    {
        dp[j] = max(dp[j],dp[j - goods.v] + goods.w);
    }
}
 
/*
    假设 物品 等于 下标

    那么背包会得到的集合是：
    
    {1} 
    {1,2} , {2}
    {1,2,3} , {2,3} , {3}
    ....
    
    获取的集合中不会出现 {2,1}... 等集合

    说明 先遍历物品再遍历背包是一个  组合 数
  
*/

②先遍历背包再遍历物品

for(int j = goods[i].v;j <= v;++j)    // 遍历背包
{
    for(int i = 0;i < goods.size();++i)    // 遍历物品
    {
        dp[j] = max(dp[j],dp[j - goods.v] + goods.w);
    }
}
 
/*
    假设 物品 等于 下标

    那么背包会得到的集合是：
    
    {1} 
    {1,2} , {2，1} ，{2}
    ....
    
    获取的集合中会出现 {2,1}... 等集合

    说明 先遍历物品再遍历背包是一个  排列 数
  
*/

所以背包问题遍历顺序中：

先遍历物品再遍历背包：组合数。

先遍历背包再遍历物品：排列数。

综上所述。

代码详解如下：

inline int change(int& amount, vector<int>& coins) 
{
    vector<int>dp(amount + 1,0);
    dp[0] = 1;    // dp 初始化  凑成 0 有 1种方法 就是 +0
    
    // 组合数遍历
    for(int &i:coins)    // 遍历物品
    {
        for(int j = i;j <= amount;++j)    // 遍历背包
        {
            dp[j] += dp[j - i];    // dp 递推公式
        }
    }
    return dp[amount];    // 返回结果
}