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

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

转换成capacity=sum/2的01背包

class Solution {
public:
    int lastStoneWeightII(vector<int>& sts) {
        int sum=0;
        for(auto i:sts)sum+=i;
        int cap=sum/2;
        int n=sts.size();
        int dp[n][cap+1];
        
        memset(dp,0,sizeof dp);
        for(int i=0;i<n;i++){
            for(int j=0;j<=cap;j++){
                if(j<sts[i]){
                    if(i)dp[i][j]=dp[i-1][j];
                }else{
                    if(i)dp[i][j]=max(dp[i-1][j],dp[i-1][j-sts[i]]+sts[i]);
                    else dp[i][j]=sts[i];
                }
            }
        }

        return sum-2*dp[n-1][cap];
    }
};

空间优化
01背包的空间优化是j倒着来
for(int j=cap;j>=sts[i];j--)
完全背包的空间优化是正着来

class Solution {
public:
    int lastStoneWeightII(vector<int>& sts) {
        int sum=0;
        for(auto i:sts)sum+=i;
        int cap=sum/2;
        int n=sts.size();
        int dp[cap+1];
        
        memset(dp,0,sizeof dp);
        for(int i=0;i<n;i++){
            for(int j=cap;j>=sts[i];j--){
                dp[j]=max(dp[j],dp[j-sts[i]]+sts[i]);
            }
        }

        return sum-2*dp[cap];
    }
};