最后一块石头的重量 II
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int i : stones){
sum += i;
}
int target = sum>>1;
int[] dp = new int[target+1];
for(int i =0; i < stones.length;i++){
for(int j = target; j >= stones[i];j--){
dp[j] =Math.max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return sum - 2*dp[target];
}
}
思路
这道题和分割等和子集都用到了0 1 背包问题，回顾一下 0 1 背包问题，到底是如何转化的。
什么是 0 1 背包问题有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
如何套用本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。和分割等和子集很像， 最多能放多少石头，或者是最大和为多少。
本题物品的重量为stone[i]，物品的价值也为stone[i]。
对应着01背包里的物品重量weight[i]和 物品价值value[i]。
最后得出结果的时候就是 sum - 2*dp[target]
