[dp19_01背包] 目标和 | 最后一块石头的重量 II
目录
1.目标和
题解
2.最后一块石头的重量 II
题解
1.目标和
链接： 494. 目标和
给你一个非负整数数组 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示例 2：
输入：nums = [1], target = 1
输出：1这道题目 我们之前用 dfs 写过
class Solution {
public:int ret;int findTargetSumWays(vector<int>& nums, int target) {dfs(nums,target,0,0);return ret;}void dfs(vector<int>& nums,int target,int pos,int path){if(pos==nums.size()){if(path==target)ret++;return;}dfs(nums,target,pos+1,path+nums[pos]);dfs(nums,target,pos+1,path-nums[pos]);}
};我们现在能不能对我们写的 dfs 优化一下呢，用背包就可以啦
题解
如果我们直接就用动态规划解决你发现状态表示、状态转移方程非常难。
所以我们先把上面问题转换一下。
- 大圆圈表示这一堆数，我们在这堆数里面填上一些 " + "， " - "，那这堆数就可以分成两个类。
- 其中一类全部都是正数，另一类全都是负数。设所有正数和为a，设所有负数绝对值的和为b。
- 接下来就是给b填上一个负号，然后a和b拼成一个表达式等于target。
a - b = target
也就是说我只要能把数分成两堆，然后让左边减去右边等于target问一共有多少种分法。
- 但是如果把问题分成两堆是非常难解决的。既要考虑左边也要考虑右边。
- 这个时候我们想一下，所有的数是不是有一个和我们设为sum。这里我们已经知道
a - b = target了，其实我们也可以知道 a + b = sum。现在把两个等式连立起来。可以得到 a = （sum + target）/ 2。
- 数学转换↑
- a求出来了，右边的就不用考虑了。因为已经求出a具体的值了。
- 也就是说只要在整个数组里挑选一些数让这些数的和等于a即可，然后问一共有多少种挑法。
问题转换：
- 在数组中选一些数，让这些数的和等于 a。
问：一共有多少种选法。
- 转化后的问题怎么解决，在数组中从左往右选数，每个数都有选or不选两种情况。
- 然后让选择的数的和等于a。这就是01背包问题里面把背包装满的问题。
1.状态表示
- dp[i][j] 表示：从前 i 个数中选，总和正好等于 j，一共有多少种选法
2.状态转移方程
- 根据最后一个位置，划分情况
- 选or不选两种情况
不选 i，0 ~ i 所有选法都不选 i，那就去 0 ~ i -1 去选
选 i，所以选法都会包含 i 这个元素并且要让总和等于j，既然 nums[i] 已经选了，那去 0 ~ i - 1 就去选总和等于 j - nums[i]，注意 j >= nums[i]。
- 还有注意dp[i-1][j-nums[i]]后面是不加1的， 0 ~ i - 1所有选法都在dp[i-1][j-nums[i]]了在所有选法后面填上 i 这个元素就行了。
然后把这两种情况加起来，因为是求 的选法数
3.初始化
- 这道题我们专门说说初始化的细节问题
- 多开一行一列
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一行表示数组为空，如果数组里面没有元素，如果不选，可以凑出和为0的情况
- 第一个位置为1，但是根本凑不出和为1、2…的情况。所以第一行剩下都为0
接下来考虑第一列，第一列为空表示和为0，那数组里面的数都不选不就可以了吗。
所以初始为0。但是这道题nums[i]是从0开始的。
- 如果nums[i]可能为0，那么第一列剩下的格子的选择就多了。
- 初始化这里的位置需要先计算一下，看这个位置的值在数组对应下标的值到底是多少
- 如果对应位置nums[i]是0，那这里+1。如果非0，那这里就是 1（啥也不选也是一种选法）
但是其实这里可以不用初始化，也就是第一列除了第一格下面的不用初始化。
- 直接放在填表里面就行了。
- 因为 选了的话 其实也是看的 上一个格子
为什么不用初始化
- 回到状态转移方程，选 i 的时候，j >= nums[i]，但是nums[i] >=0，也相当于 j >= 0。
- 填表担心dp[i-1][j-nums[i]] 它会越界访问
- 但是有了先决条件 j >= nums[i]，nums[i] >=0，所以它依旧用的是它头顶的位置，绝对不会越界访问。
4.填表
- 从上往下填写每一行
5.返回值
- dp[i][j] 表示：从前 i 个数中选，总和正好等于 j，一共有多少种选法。
- 我们要的是从整个数组种选正好等于a有多少种方法，所以返回 dp[n][a]
滚动数组优化
- 借助只和上一行有关，来优化空间
- 一定要注意填表顺序的翻转，从后往前填，来防止覆盖
for(int j=targ;j>=nums[i-1];j--)条件判断也可以移到循环里，来实现剪枝
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {//a-b=target//a+b=sum//是否 存在aint sum=0;for(int n:nums)sum+=n;int targ=(sum+target)/2;
//！！！！！
//处理边界情况
if(targ < 0 || (sum + target) % 2) return 0;int n=nums.size();vector<int> dp(targ+1,0);dp[0]=1;for(int i=1;i<=n;i++){for(int j=targ;j>=nums[i-1];j--)//将第一列的 初始化，交给循环 处理了{//下表映射dp[j]+=dp[j-nums[i-1]];}}return dp[targ];}
};2.最后一块石头的重量 II
链接：1049. 最后一块石头的重量 II
有一堆石头，用整数数组 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]，这就是最优值。示例 2：
输入：stones = [31,26,33,21,40]
输出：5- 这道题如果直接用动态规划去做是很难的。状态表示都定义不出来。
所以我们先分析这道题看能不能把这道题转换一下。
假设数组中石头的重量是a、b、c、d、e，我们模拟一下选石头的过程
有没有感觉，这是不是和之前 目标和那道题类似。
- 目标和最后就在一堆数前面填上"+“，”-" 然后凑成一个数。
- 但是我们这道题不是，我们这道题如何能转换成在数前面填上"+“，”-“，相当于把一个数分成两个部分，第一个部分全都是正数，另一部分都是负数。
- 假设正数和为a，负数绝对值的和为b。我们要的是最后一块石头重量是最小。假设b >= a，就是求b - a 最小，假设a >= b也没问题，反正a和b就是前面”+“，”-"的问题。
其次我们还知道a + b 的和假设为sum。现在问题就是我们知道a和b的和，然后找到这个两个数差最小。
- 小学时学过这样一道题，给一个数，让把这个数拆成两个数，然后问这两个数相减最小是多少。
- 当两个数越接近的时候，也就是越接近 sum 的一半的时候，它们两个的差是最小的。
所以这道题我们就可以转换成：
- 在数组中选择一些数，让这些数的和尽可能的接近 sum / 2。
- 只要能求出a就能求出b，然后让它俩相减就可以了。
- 这样转换这道题就是纯纯的01背包问题。因为所有的数都面临选or不选两种情况，选了就是1，没选就是0，这就是01背包最典型的特征。
选一些数放到背包里，背包是有容量的sum/2，问选择的数在不超过sum/2的情况下，里面最大价值是多少。所以这就是典型的01背包问题。
题解
1.状态表示
- dp[i][j] 表示： 从前 i 个数中选，总和不超过 j，此时的最大和
- （因为越 趋近于一半，差值越小）
2.状态转移方程
- 根据最近一个位置，划分情况
- 选or不选两种情况
不选 i，0 ~ i 所有选法都不选 i，那就去 0 ~ i -1 去选
选 i，所以选法都会包含 i 这个元素并且要让总和不超过j，既然 nums[i] 已经选了，那去 0 ~ i - 1 就去选总和不超过 j - nums[i]，注意 j >= nums[i]。
求两种情况的最大值
3.初始化
- 多开一行一列
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一行的要初始化，第一列不用初始化的，因为这些位置的是你想用它一定是在j >= nums[i] 条件下，因此绝不不会越界访问。所以放在填表中就行了。
第一行表示数组为0的情况，要想凑成总和不超过j，当 j 是 0 的时候不选就可以了此时最大和为0。当 j 是1、2…，根本凑不成，此时最大和还是0
- 第一列 不用初始化，将 num 为 0 的情况，交给循环填表判断就可以啦
- 因为填表有判断，所以也不用担心 dp 处理越界~
4.填表
- 从上往下填写每一行
5.返回值
- dp[i][j] 表示： 从前 i 个数中选，总和不超过 j，此时的最大和
- 我们要的是的在所有数中选总和不超过sum/2，就是dp[n][sum/2]相当于我们把左边的a算出来。
- 那b = sum - dp[n][sum/2]，那最小值就是 b-a;
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//sum/2 的背包int n=stones.size();int sum=0;for(int e:stones)sum+=e;int aim=sum/2;//多开 一行一列vector<vector<int>> dp(n+1,vector<int>(aim+1,0));for(int i=1;i<=n;i++){for(int j=0;j<=aim;j++){//下标 映射dp[i][j]=dp[i-1][j];if(j>=stones[i-1])dp[i][j]=max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);}}return sum-dp[n][aim]*2; }
};滚动数组：
- 从后往前
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {//sum/2 的背包int n=stones.size();int sum=0;for(int e:stones)sum+=e;int aim=sum/2;//多开 一行一列vector<int> dp(aim+1,0);for(int i=1;i<=n;i++){for(int j=aim;j>=stones[i-1];j--){//下标 映射dp[j]=max(dp[j],dp[j-stones[i-1]]+stones[i-1]);}}return sum-dp[aim]*2; }
};