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
【代码】：
class Solution {
public int lastStoneWeightII(int[] stones) {
int n = stones.length;
int totalWeight = 0;
//计算所有石头的总重量
for (int stone : stones) {
totalWeight += stone;
}
int target = totalWeight / 2;
boolean[][] dp = new boolean[n][target + 1];
dp[0][0] = true;
if (stones[0] <= target) {
dp[0][stones[0]] = true;
}
//状态转移
for (int i = 1; i < n; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= stones[i]) {
dp[i][j] = dp[i][j] || dp[i - 1][j - stones[i]];
}
}
}
int maxWeight = 0;
for (int j = target; j >= 0; j--) {
if (dp[n - 1][j]) {
maxWeight = j;
break;
}
}
return totalWeight - 2 * maxWeight;
}
}
思路：
本题精髓就是转化为背包问题。
我们可以将石头分成两堆，假设为堆 A 和堆 B。我们的目标是使得两堆石头的重量差最小。我们可以将问题转化为在总重量不超过 totalWeight/2 的前提下，尽可能地选取石头放入堆 A。
我们定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 个石头中选取一些石头，使得它们的总重量恰好为 j 是否可能。
对于每个石头 stones[i]，我们有两种选择：选取它或者不选取它。如果我们选取了石头 stones[i]，则有 dp[i][j] = dp[i-1][j-stones[i]]，表示在前 i-1 个石头中选取一些石头，使得它们的总重量恰好为 j-stones[i] 是否可能。如果我们不选取石头 stones[i]，则有 dp[i][j] = dp[i-1][j]，表示在前 i-1 个石头中选取一些石头，使得它们的总重量恰好为 j 是否可能。
因此，状态转移方程为 dp[i][j] = dp[i-1][j] || dp[i-1][j-stones[i]]，表示在前 i 个石头中选取一些石头，使得它们的总重量恰好为 j 是否可能。
最后，我们遍历最后一行 dp[n-1]，找到最大的 j，使得 dp[n-1][j] 为 True。最后一块石头的重量为 totalWeight - 2*j。
最后，A堆的石子重量为：j。
B堆的石子重量为totalWeight - j
所以可得，abs(A-B) = totalWeight - 2 * j文章来源：https://www.toymoban.com/news/detail-645021.html
而这个也正是最后无法合并，剩下的石子重量。文章来源地址https://www.toymoban.com/news/detail-645021.html
到了这里，关于Leet code1049 最后一块石头的重量II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
