今天继续学习动态规划解决01背包问题。

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

有一堆石头，用整数数组 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]，这就是最优值。

思路：

1.既然要使得最后剩下的石头重量最小，那么自然我们要尽可能地让重量相近的石头相撞，但如果一个一个地去配对重量相近的石头然后让其相撞，这样找下去一旦数量较多难免会比较困难。

那么我们换一种思维，反正最后都要碰得只剩一个石头，我们不如将所有石头分成两组，让一组石头变为一个大石头整体，让两个整体直接相撞得到最终剩下的那个石头。

那么如何分组呢？既然要尽可能让重量相近，那么我们统计一下总和，再将其除以2就是我们的目标分组和了。

分析到这里，已经可以抽象为背包问题，我们要将容量为目标分组和的背包尽可能的装满（注意区分Day45的那道分割等和子集是判定能不能装满）

2.首先确定dp数组含义，i为背包容量，dp[i]表示容量为i的背包所能容纳的最大价值（注意本题中石头重量等于其价值）

3.然后确定递推公式，对于当前石头有两种情况——放入背包或者不放入背包，如果放入背包那就是dp[i - stones[i]] + stones[i]；如果不放那就是dp[i]，对这两者取最大值即为dp[i]。

4.然后确定初始化，因为题目中给出元素最多有30个，单个元素最大为100，因此目标和最大为1500，我们将dp数组容量初始化为1501，又因为递推公式中涉及最大值，因此我们全部初始化为0。

5.然后确定遍历顺序，依然是先遍历物品再遍历背包（防止对于背包只能装一个物品），且背包一定要倒序遍历（防止同一个物品多次放入背包中）

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {vector<int> dp(1501,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 - 2 * dp[target];}
};

启发：

1.本题与Day45的那道分割等和子集思路相似，但要求的问题是不同的，一个是判断能不能装满背包，一个是要求尽可能装满背包，对于题目所要求的问题一定要分析清楚。

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

思路：

1.本题对个人来说是一道比较困难的题目，一开始完全没思路的那种（）。最开始想到的是通过排列组合加减号的位置计算，但是nums[i]又不是只会等于1，此时插空是非常非常难算的。寻找目标和的类似题目又想到之前回溯法所做的 39.组和总和问题，那一题是找出所有加和等于目标和的集合，与本题尽管类似但采用同样的方法又会超时。

2.想要转化到背包问题，就要想背包容量是什么?本题中想得到背包容量属实不太好想。既然我们要放置加号和减号，那么不如由此将原数组拆分成正数和负数两组，这两组（不加符号）之和为数组总和，之差为target，由此我们可以算出正数的那一组的元素和，而这个元素和就是我们的背包容量，本题由此转化为要装满这样容量大小的背包有多少种方法。

3.首先想dp数组的含义，因为本题要求的是装满背包有多少种方法，因此dp数组含义直接定义为要装满容量为i的背包有dp[i]种方法。

4.然后想递推公式，递推公式也是有些不太好想。我们可以逐个逐个分析，拿题目中的示例举例子，背包容量计算得到为4。假设一开始我们背包中没有物品，那么此时有dp[4]种方法；假设背包中已经有一个1，那么实际上此时我们只需要装满剩下的容量3即可，因此我们有dp[3]种方法；假设背包中已经有两个1，那么实际上此时我们只需要装满剩下的容量2即可，因此我们有dp[2]种方法......由此可以推理出，dp[i] += dp[i - nums[j]]。

5.然后想初始化，本题初始化同样有一点难度，dp[0]到底是初始化为0还是1呢？通过递推公式，如果我们初始化为0，那么之后所有的dp[i]全部都会为0（因为全部的dp都是由dp[0]推出的），因此我们只能初始化为1。非要解释的话，对于容量为0的背包什么 也不放就是一种装满它的方法。

6.最后是遍历顺序，由于使用的一维dp数组因此一定要先物品后背包，且背包一定要倒序遍历

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((sum + target) % 2 != 0 || abs(target) > sum) return false;int bagSize = (sum + target) / 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 - nums[i]];}}return dp[bagSize];}
};

启发：

1.即使想出了以上，最后还是难免有一些小细节需要注意：（1）如果target的绝对值大于sum了，那显然不可能得到结果；（2）如果target+sum为奇数，此时无法整除2，那么最终也一定不可能得到一个符合结果的背包容量。

2.本题思路比较复杂，一定要多加理解，想到怎么将其转化为背包问题的，又是怎么找到递推公式的。

3.对于找装满背包有几种方法的问题，递推公式一般均为dp[i] = dp[i - nums[j]]，但不能完全套用，一定要根据题目灵活变通。