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

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

---

一、题目

有一堆石头，用整数数组 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

提示：

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

二、题解

方法一：01背包二维数组

算法思路

01背包问题回顾

在01背包问题中，我们有一组物品，每个物品有两个属性：重量和价值。背包有一个固定的容量，我们的目标是在不超过背包容量的情况下，选择物品放入背包，使得放入的物品总价值最大。

我们可以将这个问题的状态定义为 dp[i][j]，表示在前 i 个物品中，背包容量为 j 的情况下，可以获得的最大价值。状态转移方程可以表示为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

将题目映射到01背包

现在我们回到题目中，虽然题目描述中没有直接提到背包，但我们可以通过观察发现类似的特性：我们要将石头分成两堆，使得两堆的重量差尽量小。

在01背包问题中，我们选择物品放入背包的状态是离散的：要么放入，要么不放入。在本题中，我们可以类比，将石头看作是我们要选择放入背包的“物品”，每块石头的重量看作是物品的“重量”。我们要将石头分成两堆，使得两堆的重量差尽量小，相当于在一个背包的容量为总重量的一半时，选择一些石头放入背包，使得背包中的石头总重量尽量接近总重量的一半。

（这里的背包容量就对应着总重量的一半，而每块石头的重量和价值相同）。这就是为什么我们能够将这个问题映射到01背包问题。

具体实现

1. 状态定义： 定义一个二维数组 dp[i][j]，表示在前 i 块石头中，能否找到一种分法，使得其中一组的总重量恰好为 j。这里 i 的范围是从 0 到石头的总数，j 的范围是从 0 到总重量的一半（因为我们要将石头分成两组，两组的重量和不能超过总重量的一半，否则不符合题意）。

2. 状态转移： 对于每一块石头，我们可以选择将其放入其中一组，或者不放入。如果我们不放入第 i 块石头，那么问题就转化为在前 i-1 块石头中寻找一种分法，使得其中一组的总重量恰好为 j。如果我们放入第 i 块石头，那么问题就转化为在前 i-1 块石头中寻找一种分法，使得其中一组的总重量恰好为 j - stones[i]。

   综合考虑这两种情况，我们可以得到状态转移方程：

   dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i]]
   

3. 边界条件： 初始化时，当只有一块石头可选时，如果这块石头的重量不超过 j，那么我们可以将其放入其中一组，否则不放入。

4. 最终结果： 最终的答案应该是在所有可能的总重量 j 中，找到最大的 j，使得 dp[n-1][j] 为 true（n 为石头的总数）。然后最小可能的剩余重量就是 sum - 2 * j。

根据上述思路，可以实现出解题代码：

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for (int i = 0; i < stones.size(); i++) {sum += stones[i];}int n = stones.size();vector<vector<int>> dp(n, vector<int>(sum / 2 + 1, 0));// 初始化for (int i = 0; i <= sum / 2; i++) {if (stones[0] <= i) {dp[0][i] = stones[0];}}// 填写dp数组for (int i = 1; i < n; i++) {for (int j = 1; j <= sum / 2; j++) {if (stones[i] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);}}}return sum - 2 * dp[n - 1][sum / 2];}
};

方法二：01背包一维数组

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for (int i = 0; i < stones.size(); i++) {sum += stones[i];}vector<int> dp(sum/2+1, 0);// 填写dp数组for (int i = 0; i < stones.size(); i++) {for (int j = sum/2; j >= stones[i]; j--) {  dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);}        }return sum - 2 * dp[sum/2];}
};

Q：为什么 for (int j = sum/2; j >= stones[i]; j–)要倒序遍历？

A：我们从前往后遍历石头，同时从总重量的一半开始递减遍历，这是因为我们想在填写 dp[j] 时，基于之前的状态 dp[j-stones[i]] 进行更新。如果我们从小到大遍历 j，那么在填写 dp[j] 时，我们可能会使用当前石头的重量（stones[i]），而这就会导致重复使用同一块石头，与题意不符。

所以，倒序遍历 j 可以确保在填写 dp[j] 时，我们只会考虑之前的状态，而不会用到当前石头。这是为了避免在填写 dp[j] 时，使用当前石头导致重复计算的情况。

Q：为什么一定要先遍历石头重量这一行然后遍历重量那一列？

A：这是为了确保状态转移方程的正确性。让我们通过一个例子来理解。

假设我们有以下石头的重量：stones = [2, 7, 4]。

我们想要使用动态规划找到一种分法，使得其中一组的总重量尽量接近总重量的一半。在此例中，总重量是 2 + 7 + 4 = 13，所以我们希望找到一种分法，使得其中一组的重量接近 13 / 2 = 6。

现在，假设先遍历重量（j），再遍历石头（i)。在这种情况下，第一次遍历（j = sum/2，i从0到stones.size()）后我们的动态规划状态数组如下所示：

stones = [2, 7, 4]
dp[i][j]:0   1   2   3   4   5   6      2:     0   0   0   0   0   0   4      7:     0   0   0   0   0   0   4      4:     0   0   0   0   0   0   4      

在这种遍历顺序下，最后一列一直到最后都不会再更新了，显然是一个错误的遍历顺序。