Java教程

最后一块石头的重量II

本文主要是介绍最后一块石头的重量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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!