代码随想录 | 刷题-动态规划4

发表于 更新于 分类于

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

  • 目标：将所有石头分成两组，使两组总重量尽量接近，最后剩下的石头重量就是两组重量差的绝对值。
  • 转化为01背包问题：每个石头只能选一次，背包容量为所有石头重量和的一半，尽量让一组的重量最大且不超过容量。
  • 为什么倒序遍历：
    • 在01背包中，正向遍历会导致同一个物品被多次使用（即变成完全背包），而倒序遍历可以保证每个物品只用一次。
    • 例如：stones = [2, 3, 5]，如果正向遍历，dp[4]=dp[2]+2=4，石头2被用了两次，违背了01背包的约束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        int hlf_sum = 0;
        for(int s: stones){
            sum += s;
        }
        hlf_sum = sum / 2; // 注意hlf_sum / 2是向下取整的

        vector<int> dp(1501, 0); // 一定要保证dp[j]是可以比较的，所以我们选择重量为j
        for(int i = 0; i<stones.size();i++){
            for(int j = hlf_sum; j>=stones[i]; j--){
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        
        return sum - dp[hlf_sum] * 2;
    }
};