力扣 -- 1049. 最后一块石头的重量 II（01背包问题）

参考代码：

未优化代码：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n=stones.size();
        int sum=0;
        for(const auto& e:stones)
        {
            sum+=e;
        }
        int aim=sum/2;
        //多开一行，多开一列
        vectorint>> dp(n+1,vector<int>(aim+1));
        //第一行和第一列的初始化都不用做，具体原因看图
        for(int i=1;i<=n;i++)
        {
            //第一列要在填表时填写，所以这里的j要从0开始
            for(int j=0;j<=aim;j++)
            {
                //状态转移方程
                dp[i][j]=dp[i-1][j];
                if(j>=stones[i-1])
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        }
        //返回值
        return sum-dp[n][aim]-dp[n][aim];
    }
};

优化代码：

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n=stones.size();
        int sum=0;
        for(const auto& e:stones)
        {
            sum+=e;
        }
        int aim=sum/2;
        //多开一行，多开一列
        vector<int> dp(aim+1);
        //第一行和第一列的初始化都不用做，具体原因看图
        for(int i=1;i<=n;i++)
        {
            //第一列要在填表时填写，所以这里的j要从0开始
            for(int j=aim;j>=stones[i-1];j--)
            {
                dp[j]=max(dp[j],dp[j-stones[i-1]]+stones[i-1]);
            }
        }
        //返回值
        return sum-dp[aim]-dp[aim];
    }
};

你学会了吗？？？