长沙网站的优化,微信小程序商城怎么开发,淘客二级域名网站免费建设,psd简单的网站首页1049. 最后一块石头的重量 II 文章目录 [1049. 最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/)一、题目二、题解方法一#xff1a;01背包二维数组算法思路具体实现 方法二#xff1a;01背包一维数组 一、题目
有一堆石头#xff0c;用整数数…1049. 最后一块石头的重量 II 文章目录 [1049. 最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/)一、题目二、题解方法一01背包二维数组算法思路具体实现 方法二01背包一维数组 一、题目
有一堆石头用整数数组 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 301 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背包问题。
具体实现 状态定义 定义一个二维数组 dp[i][j]表示在前 i 块石头中能否找到一种分法使得其中一组的总重量恰好为 j。这里 i 的范围是从 0 到石头的总数j 的范围是从 0 到总重量的一半因为我们要将石头分成两组两组的重量和不能超过总重量的一半否则不符合题意。 状态转移 对于每一块石头我们可以选择将其放入其中一组或者不放入。如果我们不放入第 i 块石头那么问题就转化为在前 i-1 块石头中寻找一种分法使得其中一组的总重量恰好为 j。如果我们放入第 i 块石头那么问题就转化为在前 i-1 块石头中寻找一种分法使得其中一组的总重量恰好为 j - stones[i]。 综合考虑这两种情况我们可以得到状态转移方程 dp[i][j] dp[i-1][j] || dp[i-1][j-stones[i]]边界条件 初始化时当只有一块石头可选时如果这块石头的重量不超过 j那么我们可以将其放入其中一组否则不放入。 最终结果 最终的答案应该是在所有可能的总重量 j 中找到最大的 j使得 dp[n-1][j] 为 truen 为石头的总数。然后最小可能的剩余重量就是 sum - 2 * j。
根据上述思路可以实现出解题代码
class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum 0;for (int i 0; i stones.size(); i) {sum stones[i];}int n stones.size();vectorvectorint dp(n, vectorint(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(vectorint stones) {int sum 0;for (int i 0; i stones.size(); i) {sum stones[i];}vectorint dp(sum/21, 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/2i从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 在这种遍历顺序下最后一列一直到最后都不会再更新了显然是一个错误的遍历顺序。
