01背包

01背包问题：对于一个背包，容量为c一共有N种物品，物品i满足价值为v[i]重量为w[i]
求：往背包中放置物品，在容量限制条件下，求得价值的最大值

经典解法：
（注意这个不超过）
定义：DP[i][j]为到第i个物品时，目前重量不超过j时，能够获得的价值最大值
对于枚举到每一个物品i有且只有三种情况：

  1. 选：那么我们此时的状态应该变为DP[i-1][j-w[i]] + v[i]，即查找上一次选取的总重量为j-w[i]的最大值，将其加上现在的重量，那么根据定义就应该是最优解
  2. 不选：这个简单，DP[i-1][j]不变即可
  3. 选不了：这种情况是因为，我们剩下的可选容量j小于物品重量w[i]

因此转移方程为：DP[i][j] = max{DP[i-1][j], DP[i-1][j-w[i]] + v[i]}

  1. // 01背包问题经典解法:
  2. // n件物品，重量约束为c，价值为v，重量为w
  3. pub fn max_value(n: usize, c: usize, v: &[usize], w: &[usize]) -> usize {
  4.     // 定义dp[i][j]为第i件物品时，重量为j时的最大价值
  5.     let mut dp = vec![vec![0; c+1]; n];
  6.     // 处理第一件物品,注意是挑选第一件物品的所有情况，那么对于重量就存在多种可能
  7.     // 对于第一件物品，初始化为大于大小的时候就选，这对于只有一件物品的时候是
  8.     // 逻辑完善的。
  9.     for size in 0..=c {
  10.         if size >= w[0] { dp[0][size] = v[0]; }
  11.     }
  13.     // 一般情况：
  14.     (1..=n).for_each(|thing| {
  15.         (0..=c).for_each(|size| {
  16.             // 如果不放：
  17.             let n = dp[thing-1][size];
  18.             // 大于的时候
  19.             let temp = if size >= w[thing] {
  20.                 dp[thing-1][size-w[thing]] + v[thing]
  21.             }else { 0 };
  22.             dp[thing][size] = max(n, temp);
  23.         }) 
  24.     });
  26.     dp[n-1][c]
  27. }

优化为一维，经典第二维倒过来遍历：

  1. // 优化：
  2. pub fn max_value_better(n: usize, c: usize, v: &[usize], w: &[usize]) -> usize {
  3.     // 定义dp[i][j]为第i件物品时，重量为j时的最大价值
  4.     let mut dp = vec![0; c+1];
  5.     // 处理第一件物品,注意是挑选第一件物品的所有情况，那么对于重量就存在多种可能
  6.     // 对于第一件物品，初始化为大于大小的时候就选，这对于只有一件物品的时候是
  7.     // 逻辑完善的。
  8.     for size in 0..=c {
  9.         if size >= w[0] { dp[size] = v[0]; }
  10.     }
  12.     // 一般情况：
  13.     (1..=n).for_each(|thing| {
  14.         (0..=c).rev().for_each(|size| {
  15.             // 如果不放：
  16.             let n = dp[size];
  17.             // 大于的时候
  18.             let temp = if size >= w[thing] {
  19.                 dp[size-w[thing]] + v[thing]
  20.             }else { 0 };
  21.             dp[size] = max(n, temp);
  22.         })
  23.     });
  25.     dp[c]
  26. }

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
问题转换为：从一个非空数组中取出一半的数据，其和为数组和的一半

定义：数组和为sum，数组长度为len，DP[i][j]为第i个数情况下，和为j，是否满足条件，即里面存储bool变量

  1. 选：DP[i][j] = DP[i-1][j-nums[i]]
  2. 不选：DP[i][j] = DP[i-1][j]
  3. 选不了：j < nums[i]
  4. 成功：即初始化DP[0][nums[0]] = true前提是nums[0] <= sum/2，此外如果DP[i][j]刚好凑齐的时候也能够成功

以bool表示不太合适，比较难写，修改定义为DP[i][j]为前i个数中，和不超过j时的最大价值（最大和）：

  1. 选：DP[i][j] = DP[i-1][j-nums[i]] + nums[i]
  2. 不选：DP[i][j] = DP[i-1][j]
  3. 选不了：j < nums[i]
  4. 成功：即初始化DP[0][nums[0]] = true前提是nums[0] <= sum/2，此外如果DP[i][j]刚好

直接看优化后的代码：

  1. /// 416. 分割等和子集
  2. pub fn can_partition(nums: Vec<i32>) -> bool {
  3.     let sum: i32 = nums.iter().sum();
  4.     if sum % 2 == 1 { return false; }
  5.     let target = sum as usize >> 1;
  6.     // 定义dp,注意sum一定是大于0的数
  7.     let mut dp = vec![0; target + 1];
  8.     // 初始化：
  9.     for i in 0..=target {
  10.         if nums[0] as usize <= i  { dp[i] = nums[0]; }
  11.     }
  12.     for i in 1..nums.len() {
  13.         for j in (0..=target).rev() {
  14.             // 不变的时候
  15.             let n = dp[j];
  16.             let temp = if (nums[i] as usize) <= j {
  17.                 dp[j - nums[i] as usize] + nums[i]
  18.             } else { 0 };
  19.             dp[j] = max(n, temp);
  20.         }
  21.     }
  23.     dp[target] == target as i32
  24. }

完全背包

01背包问题：对于一个背包，容量为c一共有N种物品，物品i满足价值为v[i]重量为w[i]
求：往背包中放置物品，在容量限制条件下，求得价值的最大值
完全背包问题：对于一个背包，容量为c一共有N种物品，物品i满足价值为v[i]重量为w[i]
求：往背包中放置物品，在容量限制条件下，求得价值的最大值，其中每个物品都不止一个。

279. 完全平方数

问题转换：存在 m 个数满足最后一个数i*i <= n，每个数可以选择 k 次j^2 * k < n，求能够获得和为n的最小数量

这一题的完全背包注意对比之前的不超过，仔细想想
image.png
image.png
注意这里的状态转移，对于任何一个数字（物品）i都可以取n次
这种方法是上面逻辑的表达，但是会超时，看时间复杂度就知道了：

  1. /// 279. 完全平方数
  2. pub fn num_squares(n: i32) -> i32 {
  3.     // 预处理得到所有物品：完全平方数
  4.     let n = n as usize;
  5.     let mut thing = Vec::new();
  6.     let mut t = 1;
  7.     while t * t <= n {
  8.         thing.push(t*t);
  9.         t += 1;
  10.     }
  11.     // 定义dp[i][j]为前i个([0..i])完全平方数和正好为j的最小数量
  12.     let mut dp = vec![vec![0x3f3f3f3f; n + 1]; thing.len() + 1];
  13.     // 初始化：用0个物品凑出价值为0的数量为0，直接影响dp[1][0],dp[1][1]
  14.     dp[0][0] = 0;
  16.     // 一般情况：
  17.     for i in 1..=thing.len() {
  18.         let x = thing[i - 1] as usize;
  19.         for j in 0..=n {
  20.             // 不选的时候
  21.             dp[i][j] = dp[i-1][j];
  22.             // 选的时候，存在k种动态情况
  23.             let mut k = 1;
  24.             loop {
  25.                 if k * x > j { break; }
  26.                 if dp[i][j - k*x] != 0x3f3f3f3f {
  27.                     dp[i][j] = dp[i][j].min(dp[i-1][j - k*x] + k)
  28.                 }
  29.                 k += 1;
  30.             }
  31.         }
  32.     }
  34.     dp[thing.len()][n] as i32
  35. }

优化：
很巧妙，但是是个高中生就该能够运用的等差数列：
image.png
所以直接把状态转移优化为了：DP[i][j] = min(DP[i][j], DP[i-1][j-t] + 1)
for_each比for快了老多了

  1. /// 优化
  2. pub fn num_squares_better(n: i32) -> i32 {
  3.     // 不再需要预处理
  4.     let n = n as usize;
  5.     // 定义dp[i][j]为前i个([0..i])完全平方数和正好为j的最小数量
  6.     let mut dp = vec![0x3f3f3f3f; n + 1];
  7.     // 初始化：用0个物品凑出价值为0的数量为0，直接影响dp[1][0],dp[1][1]
  8.     dp[0] = 0;
  10.     // 一般情况：直接将每个元素都涵盖在这一步去写
  11.     let mut t: usize = 1;
  12.     loop {
  13.         if t*t > n { break; }
  14.         let x = t*t;
  15.         // 确保j比x大
  16.         (x..=n).for_each(|j| {
  17.             dp[j] = dp[j].min(dp[j-x] + 1);
  18.         });
  19.         t += 1;
  20.     }
  22.     dp[n]
  23. }

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

问题建模就是：
定义一个价值为coins[i]的硬币为i，那么就是在满足总重量（总金额）等于amount情况下的最小硬币数量。
定义DP[i][j]为[0..i]种硬币条件下，构成总金额刚好为j的最少硬币数量，假设coins[i] = t

  1. 不选第i种硬币，DP[i][j] = DP[i-1][j]
  2. 选，选k个，那么就是：DP[i][j] = min(DP[i][j - 1*t] + 1,...,DP[i][j - =k*t] + k)

由完全背包的推导易知，选k个情况下是个等差数列，因此问题就是：
DP[i][j] = min(DP[i][j - 1*t] + 1, DP[i-1][j])

    /// 322.零钱兑换
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        // 定义dp为[0..i]种硬币情况下，能够得到和为j的最小数量
        let mut dp = vec![0x3f3f3f3f; (amount + 1) as usize];
        dp[0] = 0;
        (1..=coins.len()).for_each(|i| {
            let t = coins[i - 1];
            (t as usize..=amount as usize).for_each(|j| {
                dp[j] = dp[j];
                dp[j] = min(dp[j], dp[j - (t as usize)] + 1);
            });
        });
        let res = dp[amount as usize];
        return match res {
            0x3f3f3f3f => -1,
            _ => res
        }
    }

518. 零钱兑换 II

相比上一题来说，差别在于，上一题是最小数量，而这一题是求组合数，即从max/min问题转换为了不选不变选了加加情况，除此之外没什么变化：

pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
    let mut dp = vec![0; (amount + 1) as usize];
    dp[0] = 1;
    for i in 1..=coins.len() {
        let val = coins[i-1];
        for j in val..=amount {
            dp[j as usize] += dp[(j - val) as usize];
        }
    }

    dp[amount as usize]
}