最后一块石头的重量II
2021/6/6 10:24:21
本文主要是介绍最后一块石头的重量II,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接https://leetcode-cn.com/problems/last-stone-weight-ii/
本题其实就是尽量让石头分成重量相同的两堆
,相撞之后剩下的石头最小,这样就化解成01背包问题了。
接下来进行动规五步曲:
确定dp数组以及下标的含义
dp[j]表示容量为j的背包,最多可以背dp[j]这么重的石头。
确定递推公式
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
dp[j - stones[i]] + stones[i]中 又有- stones[i] 又有+stones[i],看着有点晕乎。
还是要牢记dp[j]的含义,要知道
dp[j - stones[i]]
为 容量为j - stones[i]
的背包最大所背重量。
dp数组如何初始化
既然 dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。
而我们要求的target其实只是最大重量的一半,所以可以把石头遍历一遍,计算出石头总重量 然后除2,得到dp数组的大小。
接下来就是如何初始化dp[j]呢,因为重量都不会是负数,所以dp[j]都初始化为0就可以了,这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会被初始值所覆盖。
代码为:vector<int> dp(target+1,0);
确定遍历顺序
如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒叙遍历!
for(auto weight : stones){ for(int ii=target;ii>=weight;ii--){ dp[ii]=max(dp[ii],dp[ii-weight]+weight); } }
举例推导dp数组
举例,输入:[2,4,1,1],此时target = (2 + 4 + 1 + 1)/2 = 4 ,dp数组状态图如下:
最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。
在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
以上分析完毕,C++代码如下:
时间复杂度:O(m * n) , m是石头总重量(准确的说是总量的一半),n为石头块数 空间复杂度:O(m) class Solution { public: int lastStoneWeightII(vector<int>& stones) { int sum=0; for(auto w : stones) sum+=w; int target=sum/2; vector<int> dp(target+1,0); for(auto weight : stones){ for(int ii=target;ii>=weight;ii--){ dp[ii]=max(dp[ii],dp[ii-weight]+weight); } } return (sum-dp[target])-dp[target]; } };
这篇关于最后一块石头的重量II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)