# 1049. Last Stone Weight II
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Knapsack problem`
Link: https://leetcode.com/problems/last-stone-weight-ii/
## 思路
任何一种“对消石头”的操作，最终都会转换成一种给数组元素 a b c d e f前面添加正负号的策略
所以本质上是跟[0494. Target Sum](https://hackmd.io/BBt3Z9T0Tx-vNuZzFlZpGg)很像
我们可以用DP找出所有正负号策略所能达到的target sum，最终答案就是求那个最小的且比零大的target sum.

需要特别注意的是，并不是所有的“添加正负号”的策略，都会有对应的“对消石头”的操作。比如+a+b+c+d+e+f就没有意义。但是我们所求的是最小的target （同时是正数），这是可以证明一定存在对应的“对消石头”的操作的。[具体证明](https://github.com/wisdompeak/LeetCode/tree/master/Dynamic_Programming/1049.Last-Stone-Weight-II)
## Code

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int stone:stones) sum+=stone;
        boolean[][] dp = new boolean[n][2*sum+1];
        dp[0][stones[0]+sum] = true;
        dp[0][-stones[0]+sum] = true;
        for(int i=1; i<n; i++){
            for(int j=-sum; j<=sum; j++){
                if(Math.abs(j-stones[i])<=sum) dp[i][j+sum] |= dp[i-1][j-stones[i]+sum];
                if(Math.abs(j+stones[i])<=sum) dp[i][j+sum] |= dp[i-1][j+stones[i]+sum];
            }
        }
        for(int i=sum; i<=2*sum+1; i++){
            if(dp[n-1][i]) return i-sum;
        }
        return sum;
    }
}