嘉兴建站模板系统,新开网络游戏排行,网站优化定做,手机微信打开文件是乱码1049 最后一块石头的重量II
【问题描述】 有一堆石头#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y#xff0c;且 x y。那么粉…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
而这个也正是最后无法合并剩下的石子重量。
