经典动态规划：完全背包问题 :: labuladong的算法小抄

[labuladong]

文章链接点这里：经典动态规划：完全背包问题

评论礼仪 见这里，违者直接拉黑。

[fornobugworld]

base case代码里没写dp[0][j]的情况

[EyeDroplyq]

不用写，数组不赋初值默认是0

[zenyanggongmian1995]

我前期都是显示的写出，主要是反复提醒自己按固定套路来，后面熟练了，可以也会逐渐把这里一些可以省略的代码省略掉。

[JoeyLearnsToCode]

Java中int数组创建后所有元素都默认是0，所以为0的base case就不需要再初始化了。
如果其他语言不是这样，还是需要代码初始化一下。

[NiceMartin]

如果把 第 i 物品装入背包的情况下, dp[i][j] 不是应该等于dp[i-1][j-coins[i-1]] 吗?

[Zhihuatanio]

物品时可以重复使用的，所以应该是dp[i][j-coins[i-1]]

[tiertie]

大佬，想问一下，为什么进行空间优化的时候，子集背包那题，j 需要从后往前遍历，而这里不需要呢？

[Daemoonn]

从前往后迭代j，相当于dp[j-coins[i]]在第i次迭代算出来就马上用，其实就代表dp[i][[j-coins[i]]。
从后往前迭代j，相当于dp[j-coins[i]]是第i - 1次迭代存下来的旧的结果，其实代表dp[i - 1][[j-coins[i]]。
状态转移方程需要的是dp[i][j-coins[i]]，所以压缩成一维后从前往后迭代j。

[zhengheng36]

如果不用上一行的结果，可用从前往后，需要用到上一行的结果，就是从后往前

[Tokics]

@NiceMartin 如果把 第 i 物品装入背包的情况下, dp[i][j] 不是应该等于dp[i-1][j-coins[i-1]] 吗?

我也这么觉得。如果你决定使用这个面值的硬币，那么就应该关注如何凑出金额 j - coins[i-1]。

比如说，你想用面值为 2 的硬币凑出金额 5，那么如果你知道了凑出金额 3 的方法，再加上一枚面额为 2 的硬币，不就可以凑出 5 了嘛。

所以先dp[i-1][j-coins[i-1]] ，再加上这个面值的硬币。组合数不变。

不过从二维优化到一维之后是一样的。

[Tokics]

但是把dp[i][j - coins[i-1]]改成 dp[i-1][j-coins[i-1]] ，提交是错的！

[Zhihuatanio]

当然啦，这个题里面是可以重复使用的，所以每次都要把i给包含进去。

[JohnFuguiWang]

借个楼，这个问题也困扰了我一阵子，但现在觉得想明白了，有一个简单的思路可以和大家讨论下。
0-1背包或者这个完全背包，都可以用这种思路考虑：两种选择，一种是第i种物品不装进背包，一种是第i种物品装入背包。
选择1：第i种物品不装入背包，那么基于这个前提，第i种物品压根就不参与任务，直接把第i种物品从备选物品栏中抹掉即可，任务就变成了“只用i-1种物品装入容量为j的背包”，当前的任务即变为dp[i - 1][j]。
选择2：第i种物品装入背包，那么基于这个前提，第i种物品肯定是至少有一个在背包里边的，占用了一些容量，背包的容量现在是j-coins[i-1]。在此基础上再思考，如何用“剩下的”物品装进背包。对于0-1背包问题，第i个物品只有一个，已经在背包里边了，“剩下的”物品就是“i-1”种物品了，任务即变为dp[i-1][j-coins[i-1]]。对于这个完全背包问题，第i个物品有无数个，有一个在背包里边了，但还有无数个在背包外边可以用，故“剩下的”物品就还是“i”种物品，任务就是dp[i][j-coins[i-1]]。

[labuladong]

如果把 第 i 物品装入背包的情况下, dp[i][j] 不是应该等于dp[i-1][j-coins[i-1]] 吗?

这里每个硬币可以选用无限多次，即物品的数量是无限的，所以第 i 个物品装入一次后还是可以继续使用的，反映到状态转移方程上是 dp[i][j-coins[i-1]]。 @Tokics @NiceMartin

[labuladong]

大佬，想问一下，为什么进行空间优化的时候，子集背包那题，j 需要从后往前遍历，而这里不需要呢？

@tiertie 关于空间优化的问题，在网站搜索「对动态规划进行降维打击」这篇文章，有详细解释。

[Tokics]

感谢大佬的答复，我终于明白了。我理解的是这样的：

dp[i][j]中使用 i 的次数是 [0, +∞],当不使用 i 的时候，dp[i][j]=dp[i-1][j];
所以也是只有在不使用 i 这个硬币的时候，才会 dp[i][j-coins[i-1]] = dp[i-1][j-coins[i-1]]。假设等号左边是（A），等号右边是(B)，那么 B 就是 A 的子集！A 还包括了一部分 C。
——————
比如说，你想用面值为 2 的硬币凑出金额 5，那么如果你知道了凑出金额 3 的方法，再加上一枚面额为 2 的硬币，不就可以凑出 5 了嘛。
——————
回到这句话，这里 coins[i-1]就是 2， 我们想凑出 dp[i][5], 可以先凑出 dp[i][3], 这里是 i 而不是i-1, 否则就漏掉了使用 2 这个硬币组成 3 这个总金额的组合，就是我们上面说的，漏掉了 C。所以用 dp[i-1][3]是错的，漏了 C这个部分。

[zxcvbnmleizhe]

压缩状态是我看漏了哪一章吗大佬，有点卡不懂压缩状态

[labuladong]

@zxcvbnmleizhe 看 这篇

[zhongweiLeex]

将凑零钱II 和 凑零钱I 格式统一

• 效率不高 但是 格式统一后 就能顺势推导了
• 感谢 东哥的 思路引导，谢谢

    public int coinChange(int[] coins, int amount) {

        int[][] dp = new int[coins.length+1][amount+1];
        // coin = 0  没有钱 
        for(int j = 1 ; j <=amount;j++){
            dp[0][j] = Integer.MAX_VALUE;
        }
        //amount = 0  要凑的钱 为 0 
        for(int i = 0; i<=coins.length;i++){
            dp[i][0] = 0;
        }
        
        for(int i = 1; i<=coins.length;i++){
            for(int j = 1; j<=amount;j++){
                //注意这里需要对 Interger.MAX_VALUE 这个边界初始值进行判断
                if( j >= coins[i-1] && dp[i][j-coins[i-1]]!=Integer.MAX_VALUE ){

                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
                }else{//面额大于 要凑的钱
                    dp[i][j] = dp[i-1][j];
                }

            }
        }
        
        return dp[coins.length][amount] == Integer.MAX_VALUE ? -1: dp[coins.length][amount];
    }
}


class Solution {
    // dp[i][j] 表示 将i个硬币装入背包 ， 剩余 需要凑的钱(j)是多少
    public int change(int amount, int[] coins) {
        
        int[][] dp = new int[coins.length+1][amount+1];
        //base case
        for(int i = 0; i<= coins.length;i++){
            dp[i][0] = 1;//base case  就是要凑 0 元 说明直接每种硬币都能拿到一种可能性 就是啥也不装
        }


        for(int i = 1; i<=coins.length; i++){
            for(int j = 1;j<=amount; j++){
                if(j >= coins[i-1]){//要凑的钱 比 当前的硬币面值大
                    int a = dp[i-1][j];//依赖于前一种  当前不拿硬币  就剩余要凑 j 了
                    int b = dp[i][j-coins[i-1]];//当前拿了硬币 装入硬币了  就剩余要凑 j-coins[i-1]
                    dp[i][j] = a+b;//因为要求的是总共多少可能 组合数 需要将两种情况的组合数相加
                }else{//剩余要凑的 j 元 比 当前的硬币面值还要小 说明凑不出来 只能依赖前一种
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return  dp[coins.length][amount];
    }
}

[labuladong]

@zhongweiLeex 给你的思考点赞👍

[yaoyuanyy]

对比01背包问题和完全背包问题一个细节
// 疑问：完全背包问题中dp[i][w] = dp[i - 1][w] + dp[i][remainW] 的 dp[i][remainW] 这里为什么是 i 而不是 i-1 呢？
// 发现：完全背包中第 i 个物品是可以重复的，而 01背包中第 i 个物品是不能重复的
// 所以，完全背包中是dp[i][remainW]，而 01背包中是dp[i-1][remainW]

[PiggyCh]

@Tokics 这恰恰就是01背包和完全背包的区别
dp[i][j] = dp[i-coins[j-1]][j] +dp[i][j-1] #完全背包，可以重复使用自己
dp[i][j] = dp[i-coins[j-1]][j-1] +dp[i][j-1] #01背包，不能重复使用

[lee666-lee]

@labuladong 东哥，这里有笔误哇？
“如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i] （应该是coins[i-1]？）这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。

如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i] （应该是coins[i-1]？）这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。”

[cxw745]

我觉得dp的定义没有太说清楚。按照题解，dp[i][j]定义为前i种硬币中，能凑出j金额的总数。那么我们可以划分为两种情况：dp[i][j] = 前i-1种硬币能凑出j金额的方法（第i种硬币不选）dp[i-1][j] + 至少有一枚第i种硬币 dp[i][j-nums[i]],即分为了第i 种硬币 = 0 和第 i 种硬币 >=1 两种子集，可以覆盖完全。

[ByteBallad]

是这样的，dp[i][j]的定义确实是必须至少使用一次第i种硬币，不然dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]解释不通。

[Fjyyyyy]

@labuladong
力扣的链接挂错啦 https://leetcode.cn/problems/coin-change-2 => https://leetcode.cn/problems/coin-change-ii

[labuladong]

感谢指出，已修复

[cwdelphi]

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (auto t : coins) {
        for (int i = t; i <= amount; i++){
            dp[i] = dp[i] + dp[i - t];
        }
    }
    return dp.back();
}

[yaoyuanyy]

对比01背包问题和完全背包问题一个细节
// 疑问：完全背包问题中dp[i][w] = dp[i - 1][w] + dp[i][remainW] 的 dp[i][remainW] 这里为什么是 i 而不是 i-1 呢？
// 发现：完全背包中第 i 个物品是可以重复的，而 01背包中第 i 个物品是不能重复的
// 所以，完全背包中是dp[i][remainW]，而 01背包中是dp[i-1][remainW]

[Jeffzholy]

对于“第三步”状态转移，分享下自己的思考：

1. 有疑问的同学首先要在——每个状态下有两个选择（即有、没有i这个硬币在组合中）这个问题上达成共识
2. 在1的基础上，对于dp[i][j]不含有i硬币组合的数量应该是dp[i-1][j]，即i硬币的数量是0
3. 对于dp[i][j]含有i硬币组合数量可以是枚举的方式想：有1个i硬币的组合数量 + 有2个i硬币的组合数量 + ... 直到j的数量无法容纳更多的i硬币
4. 有 coins[i]是dp[i][j-coins[i]]种，引用原文的内容说明为什么这个是对的：想用面值为 2 的硬币凑出金额 5，那么如果你知道了凑出金额 3 的方法，添上一枚面额为 2 的硬币，就可以凑出 5，这里j-coins[i] 不是表示只有一个coins[i]在组合dp[i][j]中，而是通过正好减去 1 个coins[i]的数值保证组合中一定有coins[i]，毕竟dp[i][j-coins[i]]也是由有第i个和没有第i个两种相加的结果，在此基础上添上一个coins[i]就保证这个表示的是至少有一个coins[i]在组合中也就是表达了有coins[i]的情况

[holmeszheng2008]

我有另一种DP的思路，在每个状态下，选择是当前index的coin使用的数量，从0开始，直到remain<0结束，感觉整体的状态树是一样的，但是leetcode运行效率却差很多，求东哥指点：

class Solution {
    int[] coins;
    Integer[][] memo;
    public int change(int amount, int[] coins) {
        this.coins = coins;
        this.memo = new Integer[amount + 1][coins.length];

        return dp(amount, 0);
    }

    private int dp(int remain, int i){
        if (remain == 0){
            return 1;
        }

        if(i == coins.length){
            return 0;
        }

        if(memo[remain][i] != null){
            return memo[remain][i];
        }
        int res = 0;
        for(int num = 0; ;num++){
            int newRemain = remain - num * coins[i];
            if(newRemain < 0){
                break;
            }

            res += dp(newRemain, i+1);
        }

        memo[remain][i] = res;
        return res;
    }
}

[WindedMan]

518. 零钱兑换 II 链接的地址贴错啦 ，不是 https://leetcode.cn/problems/coin-change-2/ 而是 https://leetcode.cn/problems/coin-change-ii/

[Landon-CN]

大佬，能讲下爬楼梯的动态规划解法么？这种顺序有关的和零钱问题的区别在哪？

[daiqian0930]

爬楼梯是排序的个数，凑零钱是组合的个数。
同样是凑到3
1）2+1=3
2）1+2 =3
对于爬楼梯： 1）!= 2）
对于凑零钱：1）== 2）

[zy614582280]

思路描述的有点问题，上面说放入硬币i的dp[i][j] = dp[i][j-coins[i-1]]
但是代码里又写dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]
反正我没有看懂。

[zy614582280]

def change2(coins: List[int],
amount: int):
n = len(coins)
dp = [[0] * (amount + 1) for _ in range(n + 1)]
for i in range(len(dp)):
dp[i][0] = 1

for i in range(n + 1):
    for j in range(amount + 1):
        if j - coins[i - 1] >= 0:
            dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j]
print_matrix(dp)
return dp[n][amount]

不知道这段代码错在哪了，跑的结果就是不对

[zy614582280]

i, j for 循环的时候没有从1开始，第一列重复计算了两次

[EyeDroplyq]

对于零钱兑换II 我第一反应是用回溯算法的框架来解决，因为是一个典型的无重复可复选的组合/子集问题，但是超时，希望有人能给优化一下。

[zhangmuwuge]

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

[zenyanggongmian1995]

我的学习进度是先掌握基本的，空间压缩后面再集中起来改写： java版空间二维dp table 压缩之前的代码，声明初始化时掉了 一个new。

[zhengheng36]

对，少了一个new

[EchooWww]

想了半天好像理解了，之前的01背包用dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i-1]] 是因为我们不仅要在target里减掉第i个硬币的面额，还要排除“已经使用过i”的可能，也就是在且仅在这一个格子处使用这个硬币。而完全背包并不需要排除这种可能，在这一步使用第i个硬币并不需要保证它之前没出现过，也就是说除去我们当前要使用的这一次，在使用前已经凑出来的额度中i也是有可能存在的，所以用dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]

[diandengpao]

我有一个关于dp数组初始化的问题 即
base case 为 dp[0][..] = 0, dp[..][0] = 1
那么dp[0][0]不是重合了吗。
会影响吗。
我自己用dp数组写还没过。。。

[diandengpao]

好吧，不会影响。。

[diandengpao]

if (j - coins[i-1] >= 0)
                dp[i][j] = dp[i - 1][j] 
                         + dp[i][j - coins[i-1]];
            else 
                dp[i][j] = dp[i - 1][j];

因为 ij初始化为1，可见是不会变为[0][0]的