完全背包问题

相对于0-1背包，主要区别点在于物品可以使用无限次

0-1背包的dp状态转移方程

// 01背包
for (int i = 0; i < weight.length; i++) {
    // 从后往前遍历背包容量
    for (int j = cap; j >= weight[i]; j--) {
        dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
    }
}

完全背包的dp状态转移方程

// 完全背包
for (int i = 0; i < weight.length;; i++) {
    // 从前往后遍历背包容量
    for (int j = weight[i]; j <= cap; j++) {
        dp[j] = max(dp[j], dp[j-weight[i]] + valeu[i]);
    }
}

上面那个是先遍历物品在遍历背包容量

我们还可以从另外一个角度理解完全背包：

因为所有物品可以无限次拿，定义dp数组表示 容量为n时，所装物品的最大价值

则有 f(n) = max( f(n-i) ) 0<i<=n且需要存在物品重量等于i

则可以循环物品，针对每一个小于等于n的物品，计算f(n-i)值取最大值

即

// 先循环容量、在循环物品
for (int i = 1; i <= cap; i++) {
    for (int j = 0; j < weight.length; j++) {
        if (weight[j] <= i) {
            dp[i] = Math.max(dp[i], dp[i - weight[j]] + values[j]);
        }
    }
}

但是两种在使用的时候也有点区别

• 518. 零钱兑换 II

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

  完全背包求方案个数，要求不考虑所选物品的顺序，即求“组合数”

  这种完全背包问题就只能 先循环物品在循环背包

  因为相同容量的情况下，针对两种物品如果考虑顺序就有两种方案（先选择a在选择b或先选择b在选择a），不考虑顺序就一种（一个a一个b）

• 377. 组合总和 Ⅳ

  class Solution {
      public int combinationSum4(int[] nums, int target) {
          // dp：当目标值为n的时候数组中的组合方案数
          // 存在递推公式：f(n) = sum( f(i) ) 0<=i<n；前提条件是 nums中要存在 n-i
          // 即当数组中的元素小于等于n时，f(n-i)的和
          int[] dp = new int[target + 1];
          dp[0] = 1;
          for (int i = 1; i <= target; i++) {
              for (int num : nums) {
                  if (num <= i) {
                      dp[i] += dp[i-num];
                  }
              }
          }
          return dp[target];
      }
  }

  与上题刚好相对，考虑所选物品的顺序，即求“排列数”

  这种完全背包问题就只能 先循环背包早循环物品

  针对每一个i<n，累计f(n-i)

• 322. 零钱兑换

  class Solution {
      public int coinChange(int[] coins, int amount) {
          // 动态规划，申明dp：表示总金额n的最少硬币个数
          // 存在递推公式 f(n) = min( f(i)+1 ) 0<=i<n; 前提条件是 存在n-i面额的硬币
          // 也就是 组成f(i)的最少硬币数+一枚n-i面额的硬币
          // 即 遍历每个硬币作为n-i存在，在加上f(i)
          int[] dp = new int[amount+1];
          Arrays.fill(dp, Integer.MAX_VALUE-1);
          dp[0]=0;
          for(int i=1; i<=amount; i++){
              for(int coin: coins){
                  if(coin<=i){
                      dp[i]=Math.min(dp[i-coin]+1,dp[i]);
                  }
              }
          }
          return dp[amount]==Integer.MAX_VALUE-1?-1:dp[amount];
      }
  }

  完全背包问题求最值

  最值问题，先遍历容量在遍历物品，或者先遍历物品在遍历容量，都可以

  public int coinChange(int[] coins, int amount) {
      int[] dp = new int[amount+1];
      Arrays.fill(dp, Integer.MAX_VALUE-1);
      dp[0]=0;
      for(int i=0; i<coins.length; i++){
          for(int j=coins[i]; j<=amount; j++){
              // 先遍历物品在遍历容量，求最值
              dp[j]=Math.min(dp[j], dp[j-coins[i]]+1);
          }
      }
      return dp[amount]==Integer.MAX_VALUE-1?-1:dp[amount];
  }

• 279. 完全平方数

  class Solution {
      public int numSquares(int n) {
          /*
          完全背包问题，物品是完全平方数 1、4、9、16，背包容量是n
          存在 f(n) = min( f(n-i) ) i是小于等于n的完全平方数
          */
          int[] dp = new int[n + 1];
          for (int i = 1; i <= n; i++) {
              for (int j = 1; j*j <= i; j++) {
                  if (dp[i] == 0 || dp[i] > dp[i - j*j] + 1) {
                      dp[i] = dp[i - j*j] + 1;
                  }
              }
          }
          return dp[n];
      }
  }

  完全背包问题求最值

  最值问题，先遍历容量在遍历物品，或者先遍历物品在遍历容量，都可以

• 139. 单词拆分

  class Solution {
      public boolean wordBreak(String s, List<String> wordDict) {
          int len = s.length();
          // 完全背包：dp数组表示：是否能组成 s中前n个字符组成的字符串
          // 则有递推公式：dp[n] = true( dp[n-i] ) 0<i<=n 且需要 字串sub(n-i,n)要在字典里面
          boolean[] dp = new boolean[len + 1];
          dp[0] = true;
          for (int i = 1; i <= len; i++) {
              String str = s.substring(0, i);
              for (String word : wordDict) {
                  // 直接遍历物品，判断如果字典中元素是当前字符的后缀，则取dp[n-word.length]
                  if (str.endsWith(word)) {
                      dp[i] = dp[i - word.length()] || dp[i];
                  }
              }
          }
          return dp[len];
      }
  }

  完全背包求是否有值

  类似于最值，先遍历容量在遍历物品，或者先遍历物品在遍历容量，都可以

总结

针对完全背包问题：

主要就是在求解方案数的时候，要看下是“排列数”还是“组合数”，选择正确的遍历顺序

如果是求解最值等问题，两种遍历顺序都可以

具体看怎么容易理解，怎么容易解决问题