百度文库怎么做网站排名,微平台推广,wordpress 好的插件,开源cms管理系统文章目录 1049. 最后一块石头的重量 II题目描述动态规划 1049. 最后一块石头的重量 II
题目描述
有一堆石头#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合#xff0c;从中选出任意两块石头#xff0c;然后将它们一起粉碎。假设石… 文章目录 1049. 最后一块石头的重量 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 301 stones[i] 100
动态规划
本题其实就是尽量让石头分成重量相同的两堆相撞之后剩下的石头最小这样就化解成01背包问题了。
// 1049. 最后一块石头的重量 II#include vector // 包含vector类用于使用向量动态数组
#include iostream // 包含输入输出流库class Solution {
public:// 主函数int lastStoneWeightII(vectorint stones) {int sum 0; // 初始化石头重量之和为0// 计算所有石头重量的总和for(int i 0; i stones.size(); i) sum stones[i];// 计算重量总和的一半向下取整int tar sum / 2;// dp数组用于存储动态规划过程中的状态初始化长度为tar1并全部填充为0vectorint dp(tar 1, 0);// 动态规划计算过程目的是使得两堆石头的重量差最小for(int i 0; i stones.size(); i) // 遍历每块石头for(int j tar; j stones[i]; j--) // 从tar开始向下遍历直到能容纳当前石头重量dp[j] max(dp[j], dp[j - stones[i]] stones[i]); // 更新dp[j]为两种情况的较大值//那么分成两堆石头一堆石头的总重量是dp[target]另一堆就是sum - dp[target]。//在计算target的时候target sum / 2 因为是向下取整所以sum - dp[target] 一定是大于等于dp[target]的。//那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。return sum - dp[tar] - dp[tar];}
};解析
此问题可以转化为一个类似于背包问题的动态规划问题。考虑将石头分成两堆使得每堆的重量尽可能接近总重量的一半。dp数组的含义是dp[j]表示在不超过重量j的条件下能选出石头的最大重量。我们遍历每一块石头更新dp数组从tar开始向下遍历这样可以确保每块石头只被选用一次。最后dp[tar]就是其中一堆石头的最大可能重量总重量减去两倍的dp[tar]因为tar是总重量的一半就是最小的可能重量即最后剩下的石头的重量。
注意
dp数组采用了自底向上的迭代方式更新这样可以避免重复计算并节省空间。代码中用了max函数来确保dp数组存储的是最优解。
