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

思路

• 任何时刻，某个石头的重量永远都是若干石头加减运算的绝对值
  • 如 a-b+c
  • 合并石头都是减法，但仍可能出现+运算符，如 a-(b-c)=a-b+c
• 任何一种合并方法，最后一个石头的重量都可以表示成一种代数形式，如 a+b-c+d+e+f-g
  • 不是所有的代数形式都可以转换为一种合并方法，如 a+b+c
• 因此题目要求的就是形如 a-b-c+d+e+f-g... 的最小值
  • 可以表示成合并方法的代数形式是所有代数形式的子集，如果代数形式的最小值位于子集中那么所有代数形式的最小值一定也是子集的最小值
• 将原问题看作，挑选若干石头作为正项和负项，使得正负项之和绝对值之差最小
  • 设 S正 为正项和，S负 为负项和，S 为所有石头重量和，min(S负-S正)=min(S-2*S正)=S-2*S正(max)，且S正≤S总/2
  • 这里默认正项和小于负项和（如果不是加个负号即可，不影响绝对值）
• 进而将题目看作 01 背包，背包体积为 S/2，挑选若干石头作为正项，使得 S 正最大

class Solution {
public:
    int f[35][3010];//f[i][j]表示选前i个物品，体积不超过j的最大价值
    int lastStoneWeightII(vector<int>& stones) {
        int n=stones.size(),sum=0;
        for(auto i:stones)  sum+=i;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=sum/2;j++)
            {
                f[i][j]=f[i-1][j];
                if(j>=stones[i-1])    
                    f[i][j]=max(f[i][j],f[i-1][j-stones[i-1]]+stones[i-1]);
            }
        return sum-2*f[n][sum/2];
    }
};