1. 题目

2. 思路

(1) 动态规划

• 将所有石头分成两堆，一堆的重量为target，则另一堆的重量为sum-target，要使最后一块石头的重量最小，就要使两堆石头的重量尽可能地接近，即target尽可能地趋近于sum/2。
• 因此，该问题可以转化为如何挑出重量尽可能接近sum/2的石头子集。
• 动态规划数组dp[j]表示容量为j的背包所能装的最大重量，对于每一块石头来说，均有两种状态，要么装，要么不装。
• 对于石头i，若不装进容量为j的背包，则该背包的重量不变；若装进容量为j的背包，则该背包的重量变为容量等于j-stones[i]的背包所能装的最大重量加上石头i的重量，二者取较大值即为对于容量为j的背包来说，石头i是该装还是不该装。

3. 代码

public class Test {public static void main(String[] args) {}
}class Solution {public int lastStoneWeightII(int[] stones) {int n = stones.length;int sum = 0;for (int stone : stones) {sum += stone;}int target = sum >> 1;int[] dp = new int[target + 1];for (int i = 0; i < n; 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];}
}