【代码随想录_Day30】1049. 最后一块石头的重量 II 494. 目标和 474.一和零

以下是今日份的总结

1049 最后一块石头的重量 II
494 目标和
474 一和零

今天的题目难度不低，掌握技巧了就会很简单，尽量还是写一些简洁代码 ^ _ ^

最后一块石头的重量 II

思路：

1.确定dp数组以及下标的含义
------ dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
2.确定递推公式
------01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
------本题 ：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
3.dp数组如何初始化
------因为重量都不会是负数，所以dp[j]都初始化为0就可以了
4.确定遍历顺序
------如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
5.举例推导dp数组

值得注意的是

最后dp[target]里是容量为target的背包所能背的最大重量。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

//二维dp数组实现
   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];
    }

目标和

思路：
既然为target，那么就一定有
left - right = target
left + right = sum
left = (target + sum)/2 。
此时问题就转化为，装满容量为left的背包，有几种方法。

1.确定dp数组以及下标的含义
------ 填满j（包括j）这么大容积的包，有dp[j]种方法
_
2.确定递推公式
------dp[j] += dp[j - nums[i]]，没弄明白什么意思，记住就可以了
_
3.dp数组如何初始化
------在初始化的时候dp[0] 一定要初始化为1
_
4.确定遍历顺序
------nums放在外循环，target在内循环，且内循环倒序
_
5.举例推导dp数组

值得注意的是

dp[j] += dp[j - nums[i]];

   int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.size();i++){
            sum += nums[i];
        }
        //没有方案
        if((target+sum)%2==1||abs(target)>sum)return 0;
        int bagSize = (target + sum)/2;
        vector<int>dp( bagSize + 1,0);
        dp[0] = 1;
        for(int i = 0;i<nums.size();i++){
            for(int j = bagSize;j>=nums[i];j--){
                dp[j] = dp[j] + dp[j-nums[i]];//求组合类问题的公式，都是类似这种
            }
        }
        return dp[bagSize];
    }

一和零

思路：
本题中strs 数组里的元素就是物品，每个物品都是一个！
而m 和 n相当于是一个背包，两个维度的背包

1.确定dp数组以及下标的含义
------ dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.确定递推公式
------01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
------本题，strs里的字符串有x个0，y个1。
------所以递推公式：dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
------字符串的x和y相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）
3.dp数组如何初始化
------01背包的dp数组初始化为0就可以。
------因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
4.确定遍历顺序
------一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！
5.举例推导dp数组

值得注意的是

这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化全为0
        for (string str : strs) {
            int x = 0, y = 0;
            for (char a : str) {
                if (a == '0')//统计当前string的‘0’的个数
                    x++;
                if (a == '1')//统计当前string的‘1’的个数
                    y++;
            }
            for (int i = m; i >= x; i--) {
                for (int j = n; j >= y; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
                }
            }
        }

        return dp[m][n];
    }

写在最后

----OK，今日份的博客就写到这里，这一期的动态规划好难想，明天继续加油！！！
—还没看下期的题，但是我的栈还有一节没写；
–追不上时间进度了！！又欠了三天的（笑
-🈚️。