背包问题

背包问题分类

• 存在问题
• 排列总数
• 组合总数
• 基于存在问题的最多/少物品使用问题

存在问题/最大值问题

• 外循环物品，内循环空间

排列总数&&组合总数问题

• 问题：为什么求组合数，是外循环物品，内循环空间呢
  • 答案：因为外循环物品就相当于固定了物品出现的顺序，物品出现的顺序唯一了，那么我们就从所有的组合中找出满足条件的那些组合的个数，最后就是答案了。
• 问题：为什么求排列数，是外循环空间，内循环物品呢
  • 答案：因为这样子做，一个物品就可以出现在任意一个位置了，就会出现所有的排列的情况了。

1049. 最后一块石头的重量 II（不熟练）

答案：

• 目标：寻找把两堆石头分成差最小的两堆，则差就是答案
• 证明：
  • 我们不断地粉碎石头。每次粉碎时，记重量最大的石头所处的堆为 AA（若两堆最大重量相同则任选一堆），另一堆为 BB。从 AA 中取出重量最大的石头，BB 中任取一石头，若没有完全粉碎，则将新石头重新放入 AA。这一操作从每堆石头中减去了同样的重量，从而保证重量之差的绝对值在粉碎前后是不变的。
  • 若出现一堆没有石头，而另一堆不止一块石头的情况，记有石头的那一堆为 AA，另一堆为 BB。要继续粉碎，则需要从 AA 中取出一块石头移入 BB，然后按规则粉碎。但移入操作让重量之差的绝对值变得更小，与事实（上文加粗文字）矛盾，所以不会出现这种情况。
  • 所以，这样子到最后只会剩下一块石头，他的值就是两堆石头的差。
• 算法：
  • 01背包的存在问题
  • 求出石头总重量的一半，记录为goal
  • 找出n块石头能组合出来的小于等于goal的最大值。

518. 零钱兑换 II

算法：

• 完全背包的组合总数的问题
• 外循环物品，内循环空间，正向遍历空间
• 压缩状态后，内循环继续正向遍历
• 初始化 dp[0] = 1
• 状态转移函数 dp[i] += dp[i-coin]

279. 完全平方数(不熟练)

算法

• 完全背包的物品最少使用问题
• 外循环物品，内循环空间，正向遍历空间
• 压缩状态后，内循环继续正向遍历

• 初始化

  for (int i = 1; i <= n; i++){
    dp[i] = i;
  }

• 状态转移函数 dp[j] = Math.min(dp[j], dp[j-square]+1);

322. 零钱兑换

算法

• 完全背包的存在+最少使用物品问题
• 外循环物品，内循环空间，正向遍历空间
• 压缩状态后，内循环继续正向遍历

• 初始化

  for (int i = 1; i <= amount; i++){
    dp[i] = Integer.MAX_VALUE;
  }
  

• 状态转移函数：和279类似，加上MAX_VALUE的判断条件

494. 目标和(不熟练)

算法：

• 01背包的组合数问题
• 思路：
  • sum = a + b
  • target = a - b
  • sum - target = 2b
  • 当(sum-target % 2) == 0 并且 sum - target >= 0 时，我们的目标就是找出b有几种组合方法
• 外循环物品，内循环空间，正向遍历空间
• 压缩状态后，内循环反向遍历
• 初始化 dp[0] = 1

• 状态转移函数： dp[i] += dp[i-num];

  377. 组合总和 Ⅳ

  算法：

• 01背包的排列数问题，参考494，但是这里是排列数量, 所以外循环是空间，内循环是物品

• 重点在进阶，数组包含负数该怎么处理
  • 如果给定的数组中含有负数，则会导致出现无限长度的排列。
  • 所以要限定排列的长度才会出现有效答案。

474. 一和零(不熟练)

算法：

• 01背包的最多物品使用量的问题，两个背包的问题
• 外循环物品，内循环两层空间
• 压缩状态后，两层内循环都要反向遍历
• 初始化 -> 啥也不做
• 状态转移函数：dp[i][j] = Math.max(dp[i][j], 1 + dp[i-ones][j-zeros]);

139. 单词拆分(不熟练)

算法：

• 「完全背包」「是否存在排列」问题
• dp matrix，字符串的每个字符对应一个boolean，表示以该字符结尾的字符串是否存在排列
• hashset存字符来判断是否包含
• 外循环dp matrix，内存换字符串
• dp[0] = true;
• 状态转移函数：dp[i] |= dp[i-word.length()];

1155. 掷骰子的N种方法

算法：

• 01背包组合总数问题
• 外循环骰子，内循环空间
• 初始化 dp[0] = 1
• 状态转移函数

  int up = Math.min(f, j);
  int total = 0;
  for (int k = 1; k <= up; k++){
    total += dp[j - k]%mod;
    total %= mod;
  }
  dp[j] = total;