代码随想录算法训练营第三十七天|1049. 最后一块石头的重量 II ，494. 目标和，474.一和零

1049. 最后一块石头的重量 II - 力扣（LeetCode）

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

思路：第一步：本题如何转换成背包问题；第二步转换成背包问题之后，哪些是重量哪些是价值；

①这里注意到题目中x==y将完全粉碎，完全粉碎相较于x!=y，剩下的石头重量肯定最小，所以从结果来看，将stones分成两堆重量接近甚至相等的石头，碰撞之后会使剩下石头最小甚至没有剩下。

②背包问题中的价值也就是这里石头重量之和，我们要使装石头的重量等于全部石头的一半，遍历才会停止。背包问题中的重量相当于每个石头的重量。

解决：动态规划五步曲

1.确定dp[i]的含义；

j表示我们要装j重量的石头，j最大等于目标值；dp[j]表示当前目标是j重量情况下，能满足的最大石头重量和。

这里有点绕，可以举例说明一下，例如有三个石头2，7，4，dp[9]和dp[10]其实都等于2+7，因为如果加上4，重量会超过我们要求的目标值10，实际上dp[9]到dp[12]都等于2+7，但如果目标值是13，dp[13]=2+7+4。

2.确定递推公式；

经过上步分析我们已经知道了，dp[j]当前最大的重量其实来自于两种情况：①加上石头i，②不加上石头i，这又和之前题目类似。

dp[j]=max(dp[j]，dp[j-stones[i]]+stones[i])；

3.dp数组初始化；

因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000 。而我们要求的target其实只是最大重量的一半，所以dp数组开到15000大小就可以了。

vector<int> dp(15001,0)

4.确定遍历顺序；

遍历顺序和背包问题一维数组一样，从后向前遍历，防止重复包含。

5.举例推导dp。

输入：[2,4,1,1]，此时target = (2 + 4 + 1 + 1)/2 = 4

代码：注意返回值是sum减去两个dp[target]

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];
    }
};

494. 目标和 - 力扣（LeetCode）

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

思路：如何将本题转换成背包问题

目标targret由nums里面元素加或者减运算得出，所以我们将结果分为两个集合；一种里面都是加元素，一种都是减元素。

例如-1 + 1 + 1 + 1 + 1 = 3加法集合里是nums[1]到nums[4],减法集合里是nums[0];

设加法集合里元素和是x,那减法集合里元素和是sum-x；(sum是nums里全部元素和)；

目标值等于加法集合元素和减去减法集合元素和；target=x-(sum-x)；

最后x=(sum+target)/2，此时问题就转化为，装满容量为x的背包，有几种方法。（这一步很重要！）。这里再解释一下，只要从nums中找到元素使其的和等于x，那么nums中剩下的元素在计算target时减去，最后结果就是target。

解决：动态规划五步曲

1.确定dp[j]的含义；

首先确定j,j表示和是j，也就是背包问题里的容量,j从小到x；dp[j]就表示组成和是j的方法数量

2.确定递推公式；

如果我们要用若干个元素组成和为j的方案数，那么有两种选择：不选第i个元素或者选第i个元素。如果不选第i个元素，那么原来已经有多少种方案数就不变；如果选第i个元素，那么剩下要组成和为j - nums[i] 的方案数就等于dp[j - nums[i]]。所以两种选择相加就是dp[j]。

所以dp[j]=dp[j]+dp[j-nums[i]]；

3.dp数组初始化；

考虑极端情况，如果j=0时候，数组[0],此时方法只有1种，所以dp[0]=1；注意如果数组[0,0,0,0,0],j=0时，dp[0]并不等于1，此dp[0]非彼dp[0]，五个0组成算式等于0的方法是从初始的dp[0]=1累加起来的。没有初始化dp[0]=1，结果都会是0。

4.确定遍历顺序；

由于每次更新dp[j]都依赖于之前计算过得dp值（也就是说当前行依赖于上一行），所以我们必须从后往前遍历更新dp值（也就是说从右往左更新），否则会覆盖掉之前需要用到得值。

5.举例推导dp。

输入：nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

代码：注意目标值大于总和情况和目标值为负数并且小于负总和的情况。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        if(target>sum||(target)<(-sum)) return 0;//目标值大于总和或者小于负总和，不存在
        if ((target + sum) % 2 == 1) return 0; // 此时没有方案
        int x=(sum+target)/2;
        vector<int> dp(x+1,0);//这里需要x+1,因为0也要算
        dp[0]=1;
        for(int i=0;i<nums.size();i++){
            for(int j=x;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[x];
    }
};

474. 一和零 - 力扣（LeetCode）

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

思路：转换成01背包问题，搞清楚谁是背包，谁是物品，最大子集在背包问题中是什么？

物品：每个元素都有1和0，1和0的个数就代表该物品属性；

背包：我们知道物品是元素，那元素要放在子集里，所以子集是背包，以往我们都知道背包有容量，这里子集也“容量”，变成了m和n，也就是说装的元素含有1的个数不超过n,有1的个数不超过m；容量变成了n和m，那背包所装物品的价值就是子集的长度，问题也就是求子集的最大长度转换成了背包所装物品的最大价值。

解决：动态规划五步曲

1.确定dp[i][j]的含义；

i这里指0的数量，j这里指1的数量，最后dp[i][j]就是表示子集的元素个数。

2.确定递推公式；

获得dp[i][j]同样有两种方式，加入当前元素，dp[i-zero][j-one]+1，或者不加dp[i][j]；zero代表0的个数，one代表1的个数，并且是指当前遍历的的元素。

dp[i][j]=max(dp[i][j]，dp[i-zero][j-one]+1)；

3.dp数组初始化；

没装元素前，0和1个数以及子集长度都是0，初始化就是dp[i][j]=0。

4.确定遍历顺序；

还是从后向前遍历，注意这里i和j都需要从后向前遍历，防止元素重复加入导致0和1的个数变大。

5.举例推导dp。

以输入：["10","0001","111001","1","0"]，m = 3，n = 3为例

注意这里和二维背包并不相同，i和j都是要考虑的“容量”

代码：

class Solution {
public:
    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 zero=0;int one=0;
            for (char c : str) {//统计元素中0和1的个数
                if (c == '0') zero++;
                else one++;
            }
            for (int i = m; i >= zero; i--) { // 遍历背包容量且从后向前遍历！
                for (int j = n; j >= one; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1);
                }
            }
        }
        return dp[m][n];
    }
};