目标和种类，正负堆

这种类型的问题抽象出来就是，一堆加正号一堆是负号，因此是正负堆。然后挑选其中的正负符号添加的种类作为答案。

494. 目标和——转换为单个堆

image.png
从三叶的题解就可以比较清晰的看见思路就是，转换为只考虑负堆的情况：
另外需要注意的是，思路更倾向于是小青蛙跳台阶那种，本质上是相加而不是max替代的情况，比如没有选就是和之前的选取一样，选了的话，就是新的一个体系，把所有的情况加入进来即可。

  1. /// 目标和
  2. pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
  3.     let sum = nums.iter().sum::<i32>() - target;
  4.     // 两种特殊情况：其中第二种重要，非2的倍数的话，代表推导式子不成立
  5.     // 如果不成立的话，是一定凑不出来的
  6.     if sum < 0 || (sum & 1) != 0 { return 0; }
  7.     // 获取到目标的负号堆需要的和，因此转换为01背包，问题变为选进负号堆或者不选
  8.     let neg = sum >> 1;
  10.     // 定义dp[i][j]为第i个数，得到负数和为j的情况
  11.     let mut dp = vec![vec![0; neg as usize + 1]; nums.len() + 1];
  12.     dp[0][0] = 1;
  13.     for i in 1..=nums.len() {
  14.         let num = nums[i-1];
  15.         for j in 0..=neg as usize {
  16.             // 注意这里的情况：如果是j比nums小的话，那么是一定不能加上去的
  17.             dp[i][j] = dp[i-1][j];
  18.             // 只有大于等于的情况，才能够加上去，然后加上去不是max而是直接加
  19.             // dp[i][j] = dp[i-1][j].max(dp[i-1][j-nums[i]]);
  20.             if j as i32 >= num { 
  21.                 dp[i][j] += dp[i-1][(j as i32 - num) as usize]; 
  22.             }
  23.         }
  24.     }
  25.     dp[nums.len()][neg as usize]
  26. }
  29. pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
  30.     let sum = nums.iter().sum::<i32>() - target;
  31.     // 两种特殊情况：其中第二种重要，非2的倍数的话，代表推导式子不成立
  32.     // 如果不成立的话，是一定凑不出来的
  33.     if sum < 0 || (sum & 1) != 0 { return 0; }
  34.     // 获取到目标的负号堆需要的和，因此转换为01背包，问题变为选进负号堆或者不选
  35.     let neg = sum >> 1;
  37.     // 定义dp[i][j]为第i个数，得到负数和为j的情况
  38.     let mut dp = vec![0; neg as usize + 1];
  39.     dp[0] = 1;
  40.     for i in 1..=nums.len() {
  41.         let num = nums[i-1];
  42.         for j in (0..=neg as usize).rev() {
  43.             if j as i32 >= num {
  44.                 dp[j] += dp[(j as i32 - num) as usize];
  45.             }
  46.         }
  47.     }
  48.     dp[neg as usize]
  49. }

1049. 最后一块石头的重量 II

这一题本质上是，给一些数加+一些数加-，使得最后得到的target最小，比对上面的一题，区别在于，上面一题是给定了target，求方案数。
因此思路就是：联系到目标和，然后解决新问题
image.png
上面是联系的思路，下面是不同的地方：
image.png
分析到这里就是，不管怎么放回，怎么进行进一步的重新碰撞，本质上只不过是两个堆石子的碰撞，那么核心的问题就变成了，如何更好的分配出这两个堆，那么思路就可以出来了，结合上一题，问题转换为，我只需要考虑一个石子堆即可。
这个石子堆最好的情况是什么呢？两边的和相等，此时碰撞之后，结果为下界0，最坏的情况呢？为sum，即只有一个堆，但明显不可能。此时问题就变回了01背包：
image.png

  1. /// 1049. 最后一块石头的重量 II
  2. pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
  3.     let sum = stones.iter().sum::<i32>();
  4.     // 不需要考虑是否能被2除尽的情况，因为相比上一题这里目标值不确定
  5.     let t = ((sum + 1) >> 1) as usize;
  6.     // 注意看笔记是如何转换为01背包问题的
  7.     let mut dp = vec![vec![0; t+1]; stones.len()+1];
  9.     for i in 1..=stones.len() {
  10.         let num = stones[i-1];
  11.         for j in 0..=t {
  12.             // 注意，这里不是求路径这种情况，因此就不是+了，而是max
  13.             dp[i][j] = dp[i-1][j];
  14.             if j as i32 >= num {
  15.                 dp[i][j] = dp[i][j].max(dp[i-1][(j as i32 - num) as usize] + num);
  16.             }
  17.         }
  18.     }
  20.     ((sum - dp[stones.len()][t]) - dp[stones.len()][t]).abs()
  21. }
  23. // 优化：
  24. pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
  25.     let sum = stones.iter().sum::<i32>();
  26.     // 不需要考虑是否能被2除尽的情况，因为相比上一题这里目标值不确定
  27.     let t = ((sum + 1) >> 1) as usize;
  28.     // 注意看笔记是如何转换为01背包问题的
  29.     let mut dp = vec![0; t+1];
  31.     for i in 1..=stones.len() {
  32.         let num = stones[i-1];
  33.         for j in (0..=t).rev() {
  34.             // 注意，这里不是求路径这种情况，因此就不是+了，而是max
  35.             if j as i32 >= num {
  36.                 dp[j] = dp[j].max(dp[(j as i32 - num) as usize] + num);
  37.             }
  38.         }
  39.     }
  41.     ((sum - dp[t]) - dp[t]).abs()
  42. }

两个约束的

474. 一和零

这一题的关键就是同时有两个约束的维度，以前是只有一个重量，现在是一个零一个一的维度，因此原始写法就会变成三维。但这一题也不是完全独立的两个约束维度，而是有交叉的，因此本质上还是一个约束，只是写法有所不同。
问题的建模还是01背包问题
image.png
直接上手一维背包写法：

  1. /// 474. 一和零
  2. pub fn find_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
  3.     fn count(input: String) -> (usize, usize) {
  4.         let (mut c0, mut c1) = (0, 0);
  5.         c0 = input.chars().fold(0, |mut acc, x| {
  6.             acc += if x == '0' { 1 } else { 0 };
  7.             acc
  8.         });
  9.         c1 = input.len() - c0;
  10.         (c0, c1)
  11.     }
  12.     let mut dp = vec![vec![0; n as usize + 1]; m as usize + 1];
  13.     strs.into_iter().for_each(|ss| {
  14.         let (c0, c1) = count(ss);
  15.         for i in (c0..=m as usize).rev() {
  16.             for j in (c1..=n as usize).rev() {
  17.                 dp[i][j] = dp[i][j].max(dp[i - c0][j - c1] + 1);
  18.             }
  19.         }
  20.         // println!("{:?}", dp);
  21.     });
  22.     dp[m as usize][n as usize]
  23. }