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

解题关键点

• 又是一道典型的动态规划题目，01 背包的变种
  • 首先对数组进行求和 sum，我们的目标是找到其中某个子数组，它们的和最接近且小于等于 sum / 2
  • 时间复杂度 O(n * sum)，空间复杂度 O(sum)

代码

impl Solution {
    pub fn last_stone_weight_ii(stones: Vec<i32>) -> i32 {
        // 照例，先求和
        // iterator.fold() 类似 js 中需要初始值的 reduce，可以直接拿到计算结果；而 iterator.reduce() 则会用第一项作为初始值，拿到一个 Option 的结果
        let sum = stones.iter().fold(0, |acc, s| acc + s);
        let target = sum / 2;
        let len = target as usize + 1;
        // 创建一个长度为 sum / 2 + 1 的向量
        let mut dp = vec![false; len];
        // 和为 0 是一定存在的嘛，所以置为 true
        dp[0] = true;
        for s in stones {
            // 如果大于目标值就直接跳过
            if s > target {
                continue;
            }
            // 依然是反转遍历
            for i in (0..(len - s as usize)).rev() {
                // 这里踩了坑，已经置为 true 的项就不要再更新了
                dp[i + s as usize] = dp[i + s as usize] || dp[i];
            }
        }
        // 最后找到最接近 target 的解
        let mut start = target as usize;
        while !dp[start] {
            start -= 1;
        }
        // 子数组的和是 start，另一半的和是 sum - start，把二者相减就是答案了
        sum - 2 * start as i32
    }
}

测试用例

assert_eq!(last_stone_weight_ii(vec![0]), 0);
assert_eq!(last_stone_weight_ii(vec![2]), 2);
assert_eq!(last_stone_weight_ii(vec![1, 2]), 1);
assert_eq!(last_stone_weight_ii(vec![1, 2, 3]), 0);
assert_eq!(last_stone_weight_ii(vec![1, 2, 100]), 97);
assert_eq!(last_stone_weight_ii(vec![0, 0, 100]), 100);
assert_eq!(last_stone_weight_ii(vec![0, 50, 50]), 0);
assert_eq!(last_stone_weight_ii(vec![2,7,4,1,8,1]), 1);
assert_eq!(last_stone_weight_ii(vec![31,26,33,21,40]), 5);