在本題中，我們可以知道，是要求最后石頭返還的重量，也就是，將整個數組分割成兩個子集，求讓兩個子集的差值最小。這和上一道分割整數集類似，只是需要我們返回差值。所以我們采用動態規劃01背包來做，最后將分割的兩個子集的差值返回即可。

首先我們明確dp數組的含義，就是dp[j]代表容量為j的背包的價值為dp[j]。

遞推公式也類似上一道題，采用一維01背包遞推公式即可
dp[j] = Math.max(dp[j]，dp[j-weight[i]]+values[i])。

初始化，dp[0] = 0，因為容量為0價值肯定是0，其他位置依舊取最大值可以覆蓋即可，那么就取0就可以了。

遍歷順序：01背包一維數組遍歷順序應該先遍歷物品，再遍歷背包，背包并且要從大往小遍歷。

打印數組

我們最后返回的應該是兩個部分的差值，也就是dp[target]和sum-dp[target]這兩部分的差值，sum-dp[target]一定比dp[target]大，因為dp[target]是sum/2得到的target，除法是向下取整的。

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//相當于sum/2，因為除法是向下取整，這樣比如5/2，結果應該是2，那么剩下的部分是5-5/2=3，則兩部分差值就是3-2=1//初始化dp數組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];}
}