力扣第1049题最后一块石头的重量Il c++ 动态规划（01背包）-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣第1049题最后一块石头的重量Il c++ 动态规划（01背包）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

1049. 最后一块石头的重量 II

中等

思路和解题方法

使用了 0-1 背包问题的思想，通过动态规划的方式求解。

具体思路如下：

首先，计算所有石头的总重量 sum。

然后，将问题转化为将石头分成两堆，使得两堆的重量尽可能接近 sum/2。

创建一个大小为 15001 的动态规划数组 dp，用于记录容量为 j 的背包所能装载的最大重量。

使用双重循环遍历石头数组 stones 和背包容量 j，进行动态规划的状态转移。

在每次状态转移时，比较当前背包容量 j 能够装载的最大重量 dp[j] 和将当前石头放入背包后所能得到的重量 dp[j - stones[i]] + stones[i]，取较大值更新 dp[j]。

最后，返回两堆石头的重量差值，即 sum - dp[target] - dp[target]。

复杂度

时间复杂度:

O(n*m)

时间复杂度为 O(n * m)。

其中 n 是石头的数量，m 是石头总重量的一半。这是因为代码中使用了两层循环，外层循环遍历石头数组，内层循环遍历背包容量。对于每个背包容量，都需要进行一次状态转移操作，因此总共需要进行 n * m 次状态转移。

空间复杂度

O(m)

空间复杂度为 O(m)。

其中 m 是石头总重量的一半。这是因为代码中创建了一个大小为 15001 的动态规划数组 dp，用于记录不同背包容量下的最大重量。由于背包容量的最大值为石头总重量的一半，因此数组 dp 的大小为 m+1，即 15001。因此，所需的额外空间随着石头总重量的增加而增加，但是与石头的数量无关。

需要注意的是，代码中使用了一个固定大小的动态规划数组 dp，这是因为题目给定了石头的最大数量为 30，每块石头的重量最大为 100。根据题目的限制条件，可以确定石头总重量的上限为 3000，因此背包容量的上限为 1500。为了保证数组 dp 能够覆盖所有可能的背包容量，将其大小设置为 15001。如果题目的限制条件发生变化，可能需要调整数组 dp 的大小以适应新的情况。

c++ 代码

int lastStoneWeightII(vector<int>& stones) {
    vector<int> dp(15001, 0); // 创建一个大小为 15001 的动态规划数组 dp，初始值都为 0
    int sum = 0; // 计算所有石头的总重量
    for (int i = 0; i < stones.size(); i++) {
        sum += stones[i];
    }
    int target = sum / 2; // 目标是将石头分为两堆，使得两堆的重量尽可能接近 sum/2

    for (int i = 0; i < stones.size(); i++) {
        for (int j = target; j >= stones[i]; j--) {
            // 动态规划的核心逻辑
            // dp[j] 表示容量为 j 的背包所能装载的最大重量
            // dp[j-stones[i]]+stones[i] 表示将当前石头放入容量为 j 的背包中所能得到的重量
            dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
        }
    }

    return sum - dp[target] - dp[target]; // 返回两堆石头的重量差值
}

简洁写法(使用库函数做加法)

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001,0);
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum/2;
        for(int i = 0;i<stones.size();i++)
            for(int j = target;j>=stones[i];j--)
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
        return sum - dp[target] - dp[target];
    }
};

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦 >人< 。文章来源地址https://www.toymoban.com/news/detail-741268.html

到了这里，关于力扣第1049题最后一块石头的重量Il c++ 动态规划（01背包）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！