大家好，欢迎来到IT知识分享网。

动态规划—完全背包问题详解

鸣谢：本次的学习是跟着Carl的笔记来的，原创作者为Carl，可以在b站或者公众号关注Carl，搜索代码随想录。

完全背包理论基础

1、问题

背包最大容量为4，现有下面的物品各无限个。

问：背包能背的最大物品价值是多少？

2、与01背包的区别

01背包遍历顺序的核心思路

for(int i = 0; i < weight.size(); i++) { // 遍历物品
 	for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
 		dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 	}
}

内层的循环，从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包中的物品是可以添加多次的，所以需要我们从小到大去遍历。即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
 	for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量
 		dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

3、一维dp和二维dp

01背包中⼆维dp数组的两个for遍历的先后循序是可以颠倒了，⼀位dp数组的两个for循环先后循序⼀定是先遍历物品，再遍历背包容量。

在完全背包中，对于⼀维dp数组来说，其实两个for循环嵌套顺序同样无所谓！

因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了

// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

二维dp的话，其实和之前01背包是一样的

// 初始化
    // 当j=0时，背包容量为0，最大价值为0；当i=0时，也就是前0件物品，也就是没有物品，最大价值也是0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (j - weight[i-1] < 0) // 如果当前背包容量放不下第i件物品，那么前i件物品放入背包得到的最大价值就是前i-1件物品放入获得的最大价值
                dp[i][j] = dp[i-1][j];
            else { // 如果能放下，从放和不放两种选择里取最大值，这里要注意，其实完全背包二维数组的代码跟一维只有下面一个下标不同，那就是“放i”这个选择，因为是可以重复放的，所以是dp[i]
                dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i-1]] + value[i-1]);
            }
        }

一、LeetCode-518.零钱兑换II

1、题干

2、动规思路

①确定dp数组即下标的含义

dp[j]表示当前amount为j，有dp[j]种方法可以凑成j。

②递推公式

dp[j]的来源：
dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
所以递推公式：dp[j] += dp[j - coins[i]]

求装满背包有⼏种⽅法，⼀般公式都是：dp[j] += dp[j - nums[i]]

③初始化

首先dp[0]要初始化为1，dp[0] = 1是递归公式的基础。
从dp[i]的含义上来讲就是，凑成总⾦额0的货币组合数为1

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

④遍历顺序

• 题目中要求的时组合数

  • 要区分组合数和排列数的区别
    • 比如2+2+1=5,1+2+2=5，如果是组合数，这就是一种情况，如果是排列数，这就是两种情况。

• 那么本题中，内外层的循环顺序是否可以对调呢？

  • 不可以
    • 因为在完全背包问题中，我们求的时一个总和，即不管元素之间的顺序，和顺序没有关系。
  • 而本题中要求方案数，也就是组合数，内外层的循环就很有讲究了。

• 外层遍历物品（钱币），内层遍历背包（金钱总额）情况（求组合数）

  • 代码

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

    • 对于面额为coins[i]的硬币，当coins[i]<=j<=amount时候，如果存在一种硬币组合的金额之和等于j-coins[j]，则在该硬币组合中增加一个面额为coins[i]的硬币，更新数组dp中每个大于或等于该面额的元素的值。

      例如：dp[5] = dp[4]+dp[3]+dp[0]

  • 上述做法不会重复的计算不同的排列，因为外层循环是遍历数组coins的值，内层循环是遍历不同金额之和，在计算dp[j]的值的时候，可以确保金额之和等于 j 的硬币面额的顺序.

• 外层遍历背包（金额），内层遍历物品（钱币）情况（求排列数）

  • 代码

    • 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]];
          }
      }
      

  • 在这种情况下，会出现每一个金额，都会遍历所有的钱币。此时dp[j]算出来的就是排列数。

3、代码实现

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+1;j++){
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

或者：

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=0;j<amount+1;j++){
                //判断条件要把控好
                if(j-coins[i]>=0)
                    dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

二、LeetCode-377.组合总和IV

1、题干

2、思路

从这道题的要求就可以看出，要计算的是排列数，所以我们应该把背包的容量，放在外层循环。

3、代码实现

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        
        for(int j=0;j<=target;j++){
            for(int i=0;i<nums.length;i++){
                if(j-nums[i]>=0)
                    dp[j] += dp[j-nums[i]];
            }
        }

        return dp[target];
    }
}

三、LeetCode-70.爬楼梯

1、题干

2、动规思路与题目变形

这道题在动规的时候，是按照类似斐波那契数列直接推导做的。由于当时没有学到完全背包问题，所以简单就结束了。

题目变形

题目简单的变形之后，就成为了一个完全背包的问题。

①确定dp数组下标及其含义

dp[j]：爬到第j个台阶，有dp[j]中组合（方法）

②确定递推公式

在本题之中，dp[j]的来源有：
	dp[j-1]、dp[j-2]、dp[j-3]、...dp[j-m]
递推公式为
	dp[j] += dp[j-i]

③初始化

既然递归公式是 dp[i] += dp[i - j]，那么dp[0] ⼀定为1，dp[0]是递归中⼀切数值的基础所在，如果dp[0]
是0的话，其他数值都是0了。

下标⾮0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果

④确定遍历顺序

这里求的是排列问题！！
因为1、2 步 和 2、1 步都是上三个台阶，但是这两种⽅法不⼀样。

3、代码

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        
        for(int j=0;j<=n;j++){
            for (int i=1;i<=2;i++){//这里把2换成m就可以AC题目变形
                if(j-i>=0)
                    dp[j] += dp[j-i];
            }
        }
        return dp[n];
    }
}

四、LeetCode-322.零钱兑换

1、题干

2、动规思路

上面我们已经兑换过一次零钱了，计算的是组合数。我们这次遇到的问题，也是一个完全背包问题，因为我们可以看到硬币的数量是无限的。

①确定dp数组及下标含义

dp[j]：凑出总数j，所用到的最少钱币个数是dp[j]。

②递推公式

递推公式：dp[j] = Math.min(dp[j - coins[i]] + 1, dp[j])
解释：
	得到dp[j]的方式有：当前这个硬币拿不拿两种情况
		如果当前这个硬币拿了，那么dp[j] = dp[j-coins[i]]+1 （只加1，在拿了这个硬币之后所需要的最小的硬币个数上加1（当前））
		如果当前这个硬币不拿，那么dp[j] = dp[j]，（上一次遍历硬币的结果）

③初始化

⾸先凑⾜总⾦额为0所需钱币的个数⼀定是0，那么dp[0] = 0;
其他下标对应的数值呢？
考虑到递推公式的特性，dp[j]必须初始化为⼀个最⼤的数，
	否则就会在Math.min(dp[j - coins[i]] + 1, dp[j])⽐较的过程中被初始值覆盖。
所以下标⾮0的元素都是应该是最⼤值

④遍历顺序

外层遍历硬币
	内层遍历背包
顺序从左到右
实际上，本题求得不是排列或者组合，只是一个个数的问题，所以内外层可以互换。

⑤举例推导

3、代码实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for (int i = 1; i <=amount ; i++)
            dp[i] = Integer.MAX_VALUE;

        for (int coin : coins) {
            for(int j=coin;j<=amount;j++){//从当前这个硬币的值开始遍历
                if (dp[j-coin]!=Integer.MAX_VALUE)
                    dp[j] = Math.min(dp[j],dp[j-coin]+1);
            }
        }

        if (dp[amount]==Integer.MAX_VALUE)
            return -1;
        return dp[amount];
    }
}

或者

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for (int i = 1; i <=amount ; i++)
            dp[i] = Integer.MAX_VALUE;

        for (int coin : coins) {
            for(int j=0;j<=amount;j++){
                if (j-coin>=0 && dp[j-coin]!=Integer.MAX_VALUE)//注意此处的条件是j-coin>=0
                    dp[j] = Math.min(dp[j],dp[j-coin]+1);
            }
        }

        if (dp[amount]==Integer.MAX_VALUE)
            return -1;
        return dp[amount];
    }
}

五、LeetCode-279.完全平方数

1、题干

2、动规思路

①确定dp数组及其下标的含义

dp[j]：和为j（背包容量）的完全平方数的最少数量为dp[j]（填满j所需要的最少物品）

②确定递推公式

首先小于n的完全平方数，也就是物品，就是i*i（用i代表物品）
那么，dp[j]的来源为：
	当前这个完全平方数取不取
		如果不取的话，dp[j] = dp[j]
		如果取了的话，dp[j] = dp[j-i*i]+1
所以，dp[j] = Math.min(dp[j],dp[j-i*i]+1)

③初始化

dp[0]表示 和为0的完全平⽅数的最⼩数量，那么dp[0]⼀定是0。
有同学问题，那0 * 0 也算是⼀种啊，为啥dp[0] 就是 0呢？
看题⽬描述，找到若⼲个完全平⽅数（⽐如 1, 4, 9, 16, ...），题⽬描述中可没说要从0开始，dp[0]=0完全是为了递推公式。

⾮0下标的dp[j]应该是多少呢？
从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最⼩的，所以⾮0下标的dp[i]⼀
定要初始为最⼤值，这样dp[j]在递推的时候才不会被初始值覆盖

④遍历顺序

我们知道这是完全背包，
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
在动态规划：322. 零钱兑换中我们就深⼊探讨了这个问题，本题也是⼀样的，是求最⼩数！
所以本题外层for遍历背包，⾥层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！

⑤距离推导

3、代码实现

①先遍历背包，再遍历物品。

class Solution {
    public int numSquares(int n) {
		int[] dp = new int[n+1];
        for (int i=1;i<=n;i++)
            dp[i] = Integer.MAX_VALUE;
        
        for(int j=0;j<=n;j++){//遍历背包
            for(int i=1;i*i <= j;i++){//遍历物品（i*i就是我们的物品，组合数），注意此时的小于等于号
                dp[j] = Math.min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}

②先遍历物品，再遍历背包。

class Solution {
    public int numSquares(int n) {
		int[] dp = new int[n+1];
        for (int i=1;i<=n;i++)
            dp[i] = Integer.MAX_VALUE;
        
        for(int i=1;i*i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j-i*i>=0)//注意此时的大于等于号
                    dp[j] = Math.min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}

六、LeetCode-139.单词拆分

1、题干

2、动规思路

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问能不能 把背包装满。由于拆分的时候可以重复使用字典中的残次，说明就是一个完全背包！

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

dp[j]：字符串长度为j的话，dp[j]为true，表示可以拆分为一个或者多个在字典中出现的单词

②确定递推公式

如果确定dp[j]是true，且[i,j]这个区间的字出现在字典里，那么dp[j]一定是true.
所以递推公式为：
	if([i,j]这个区间的字串出现在字典里 && dp[i]是true)
		那么dp[j] = true

③初始化

从递归公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递归的根基，dp[0]⼀定要为 true，否则递归下去后⾯都都是 false了。

那么dp[0]有没有意义呢？
dp[0]表示如果字符串为空的话，说明出现在字典⾥。

但题⽬中说了“给定⼀个⾮空字符串 s” 所以测试数据中不会出现i为0的情况，
那么dp[0]初始为true完全就是为了推导公式。

下标⾮0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为⼀个或多个在字典中出现的单词。

④确定遍历顺序

本题使用求排列的方式，还是求组合的方式都可以。
但是本题具有特殊性，因为是要求字串
	最好是遍历背包放在外循环，将遍历物品放在内循环
	如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的⼦串都预先放在⼀个容器⾥。
内循环从前向后

⑤举例推导

3、代码实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
		Set<String> wordSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int j=1;j<=s.length();j++){//遍历背包
            for (int i=0;i<j;i++){//遍历物品
                String word = s.substring(i,j);
                if(wordSet.contains(word) && dp[i]){
                    dp[j] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

4、代码分析

• 首先题目给我们的是一个列表

  • 列表存储的是有序的元素
  • 列表中元素可以重复
  • 列表中元素的顺序关系由添加到列表的前后顺序而来

• 将列表转化为集合

  • 集合是无序的
  • 集合中没有重复的元素

• 题目特征

  • 我们需要判断，物品（当前这个单词）是不是在集合当中
  • 恰好，使用Set的contains方法可以快捷的实现。