文章目录
- 1. 题目
- 2. 思路
- (1) 动态规划
- 3. 代码
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];}
}