代码随想录算法训练||1049. 最后一块石头的重量 II ||背包问题二维dp和一维dp的区别

71 阅读 0 评论 47 点赞

我是靠谱客的博主受伤夕阳，最近开发中收集的这篇文章主要介绍代码随想录算法训练||1049. 最后一块石头的重量 II ||背包问题二维dp和一维dp的区别，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

这题最重要的地方就是想到将所有石头切分成两堆大小尽可能相同的石头。两堆尽可能相同的石头相减的结果就是最终结果，如果想到了这一点那么这一道题就跟 416. 分割等和子集的解法差不多了。

动规五部曲：

1.dp[j]及其下标的定义：dp[j]当前容量为j的背包所容纳的最大容量的石头

2.dp[i]的递推公式：dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])

3.dp[i]的初始化，全部初始化为0

4.dp[i]的遍历顺序，遍历石头从前往后，遍历背包从后往前，从最大容量到当前物品的重量.（为什么？如果遍历从小到大的话，会产生一个物品重复放进背包，为什么是最大容量到当前物品的重量而不是最大容量遍历到0，因为需要考虑到当前物品的重量如果大于背包的容量，那么就放不进背包，直接跳过当前物品到遍历下一个物品，防止下标被减为负数，

5.打印dp

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(15001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) sum += stones[i];
        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];
    }
};

背包问题：

让我产生了困惑了的地方就是二维dp和一维dp的for循环遍历容量问题上，二维dp可以遍历背包容量的时候可以从大到小也可以从小到大，但是一维dp确只能从大到小遍历容量。

二维dp

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

你看二维dp的遍历表达式，大致意思就是遍历每个物品取或者不取，每一层的物品只会取一次，不会多取，dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])这个表达式保证了每层相比于上层同一个背包容量时，最多只多取一个物品，所以怎么都不会多取，因为是dp[i-1][j-weight[i]]，容量为j-weight[i]最大能容量物品多少，是上一层的数据，不同于一维数组dp[j-weight[i]]取的是这一层的数据，如果这一层加过一次那他还会再加一次。

一维dp

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

大致意思就是二维数组就是除了这个物品以外的前面物品在容量为j-weight[i]中能取的最大容量。然后一维dp如果从前往后遍历意思就是不排除当前这个物品j-weight[i]这个容量的背包能装多少物品。所以一维dp从后往前遍历就可以避免这个问题，也相当于排除当前这个物品外j-weight[i]能装下多少的最大物品，因为从大到小遍历，当前层没遍历到的地方都是上一层的数据，这样就与二维相同。

倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

不可以！

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

为什么二维数组可以将遍历背包的顺序和遍历数组的顺序给转换？

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

如上代码可以发现，调换了遍历背包和遍历物品的顺序，每次遍历dp[i][j]的时候都需要先拿到dp[i-1]时的数据，同等存储容量时，存放当前物品之前存放物品的最大值。

虽然先遍历背包，再遍历物品同样可行，但是不推荐进行这样遍历。