1049. 最后一块石头的重量 II (opens new window)

1.动规+0-1背包

分析：最后得到的结果对于每个石头而言，产生的贡献作用无非是加或者减。题目等价于在stones数组每个元素之间添加正负号，求得到的最小正数和，与494. 目标和 (opens new window)做法类似。

问题等价于将所有石头分成两堆，求解两堆相减得到的最小非负和，从而转化为0-1背包问题。每个石头都有选或者不选两种策略(注意与加或者减在dp数组更新上的区别)。dp数组求解的是所有可能得到的相加和j的方案数，因此需要继承i-1状态的结果。如果石头之和为j的方案存在，则用stonesSum减去j即可得到另一半的和。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int stonesSum=0;
        for(int i=0;i<stones.length;i++) stonesSum+=stones[i];
        int[][] dp=new int[stones.length][stonesSum+1];
        int res=Integer.MAX_VALUE;
        dp[0][0]=1;
        dp[0][stones[0]]=1;
        for(int i=1;i<stones.length;i++){
            for(int j=0;j<=stonesSum;j++){
                dp[i][j]=dp[i-1][j];
                if(j-stones[i]>=0) dp[i][j]+=dp[i-1][j-stones[i]];
                if(dp[i][j]>0) res=Math.min(res,Math.abs(stonesSum-2*j));
            }
        }
        if(stones.length==1) return stones[0];  
        return res;
    }
}