1049.md

title	description	keywords
1049. 最后一块石头的重量 II	LeetCode 1049. 最后一块石头的重量 II题解，Last Stone Weight II，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1049. 最后一块石头的重量 II 最后一块石头的重量 II Last Stone Weight II 解题思路 数组 动态规划

1049. 最后一块石头的重量 II

🟠 Medium  🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1]

Output: 1

Explanation:

We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,

we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,

we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,

we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:

Input: stones = [31,26,33,21,40]

Output: 5

Constraints:

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 100

题目大意

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出 任意两块石头 ，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]

输出：1

解释：

组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，

组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，

组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，

组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

输入：stones = [31,26,33,21,40]

输出：5

解题思路

思路一：动态规划

这道题可以转化为背包问题，有一定的难度。

题目要从石头堆中选出任意两块石头，然后将它们一起粉碎，求最后一块石头的重量。可以将问题转化为：把一堆石头分成两堆，求两堆石头重量差最小值;

进一步分析，要让差值小，两堆石头的重量都要接近 sum/2 ，我们假设两堆分别为 A、B ，A<sum/2，B>sum/2，若 A 更接近 sum/2 ，B 也相应更接近 sum/2;

进一步转化，将一堆 stones 放进最大容量为 sum/2 的背包，求放进去的石头的最大重量 MaxWeight，最终答案即为 sum-2*MaxWeight;

• 先求出所有石头的总重量 sum，则背包的重量为 target = sum / 2；
• 使用二维数组 dp，其中 dp[i][j] 表示将前 i 块石头放入容量为 j 的背包时，背包里石头的最大重量。
• 初始化第一列，表示只有一块石头 stones[0] 时，背包里石头的最大重量。
• 状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]
  • 其中，dp[i - 1][j] 表示第 i 个石头不放入背包；
  • dp[i - 1][j - stones[i]] + stones[i] 表示第 i 个石头放入背包，则对于前 i - 1 块石头，背包的容量只剩 j - stones[i]；
• 遍历石头重量和背包容量，根据状态转移方程更新 dp[i][j] 的值。
• 最后返回 sum - 2 * dp[n - 1][target]

复杂度分析

• 时间复杂度：O(n * target)，其中 n 是石头的数量，target 是石头总重量的 1/2。
• 空间复杂度：O(n * target)，使用了一个二维动态规划数组。

---

思路二：压缩状态的动态规划

• 由于二维数组中，第 i 行 dp[i][...] 只和第 i - 1 行 dp[i - 1][...] 有关，所以可以将 dp 数组压缩至一维；
• 使用一维数组 dp，其中 dp[j] 表示背包容量为 j 时的，背包里石头的最大重量；
• 初始化 dp 数组为 0；
• 状态转移方程：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]；
  • 其中，dp[j] 表示第 i 个石头不放入背包；
  • dp[j - stones[i]] + stones[i] 表示第 i 个石头放入背包，则对于前 i - 1 块石头，背包的容量只剩 j - stones[i]；
• 遍历石头重量和背包容量，根据状态转移方程更新 dp[i][j] 的值，注意，此时需要反向遍历 j，确保在更新当前状态时，所依赖的状态已经被正确计算；
• 最后返回 sum - 2 * dp[target]；

复杂度分析

• 时间复杂度：O(n * target)，其中 n 是石头的数量，target 是石头总重量的 1/2。
• 空间复杂度：O(target)，使用了一个一维动态规划数组。

代码

::: code-tabs

@tab 动态规划

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
	const sum = stones.reduce((num, acc) => acc + num, 0);
	const target = Math.floor(sum / 2);
	const n = stones.length;
	const dp = new Array(n).fill(0).map(() => new Array(target + 1).fill(0));
	// base case
	for (let j = 0; j <= target; j++) {
		if (j < stones[0]) {
			dp[0][j] = 0;
		} else {
			dp[0][j] = stones[0];
		}
	}
	for (let i = 1; i < n; i++) {
		for (let j = 1; j <= target; j++) {
			if (j < stones[i]) {
				dp[i][j] = dp[i - 1][j];
			} else {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
			}
		}
	}
	return sum - 2 * dp[n - 1][target];
};

@tab 压缩状态的动态规划

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeightII = function (stones) {
	const sum = stones.reduce((num, acc) => acc + num, 0);
	const target = Math.floor(sum / 2);
	const n = stones.length;
	const dp = new Array(target + 1).fill(0);

	for (let i = 0; i < n; i++) {
		for (let j = target; j >= 0; j--) {
			if (j >= stones[i]) {
				dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
			}
		}
	}
	return sum - 2 * dp[target];
};

:::

相关题目

题号	标题	题解	标签	难度	力扣
2035	将数组分成两个数组并最小化数组和的差		位运算 数组 双指针 4+	🔴	🀄️ 🔗