代码随想录第三十三天|动态规划part04--494.目标和、1049.最后一块石头的重量Ⅱ、474.一和零

刷题小记：

494启发我们：可以对于集合中的元素，如果它符合“要么选用，要么不用”，那就可以考虑使用动态规划来进行模拟。

昨天已提到，dp数组可以用来求这个背包能否被装满，换个角度：也能求对于装满指定背包大小的方案数。

至于1049题，也是尽可能装满指定背包的实践。而474题，则在此基础上，尝试装满一个二维的指定背包。

总结：494装满指定背包并记录其方案数（组合数）；1049尽可能装满指定背包并记录其最大价值；474尽可能装满指定背包并记录其最大价值。

494.目标和（494.目标和）

题目分析：

给定一个非负整数数组nums和整数target。现在向数组中每个整数前添加'+'或'-'，串联起所有整数构造成一个表达式，返回通过上述方法构造的、运算结果等于target的不同表达式的数目。

注意：任意两个表达式，只要有一处在nums数组中下标相同的元素前面添加的符号不同，那么这两个表达式就是不同的。

解题思路：

对于任意的nums中的数，要么为加数，要么为减数。

若nums的数组和为sum，假设表达式中加数的总和是x，那么表达式中减数的总和是-(sum - x)，则表达式的值为x - （sum - x)。

我们要求的就是x - (sum - x) =target，而x = (target + sum)/2。

此时问题就转化成：用nums数组中的元素装满加数和为x的背包有几种方法。

注意：

1. 由于(target + sum)向下取整，实际情况下若其不能被整除，则不存在非负整数x符合条件，直接返回0表示没有这样的表达式。
2. 由于x是加数的和，若Math.abs(target) > sum，显然不存在这样的非负整数x符合条件，直接返回0表示没有这样的表达式。

动规五部曲：

1. 确定dp数组以及下标含义：dp[i][j]表示使用下标为0~i之间的加数能够装满j的方法数。
2. 确定递推公式：

1. 1. 若j-nums[i] < 0，那么dp[i][j] = dp[i-1][j]
   2. 否则dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]

1. dp数组初始化：由递推公式知，需要知道上方和左上方的值

1. 1. 初始化dp数组为 new int[nums.length][x + 1]
   2. 初始化上方，及最上行，使用第一个数所能得到的加数和的情况数，为dp[nums[0]] = 1，其余自动为0
   3. 初始化左方，及最左列：

1. 1. 1. dp[i][0]表示用下标0~i之间的数选取加数，所得和为0的情况，当且仅当所有非零整数取'-'时所得和为0，而情况数即为0~i之间的零的数量numZero运算2^numZero所得。

1. 确定递推顺序：

1. 1. 从上到下，从左到右

1. 举例推导dp数组：省略。

二维版本

class Solution {int OFFSET = 1000;public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i = 0; i < nums.length; i++) {sum += nums[i];}if (sum < Math.abs(target)) return 0;// 即target的绝对值超过sum，此时无方案if ((sum + target) % 2 != 0) return 0;// 即正数和不为整数，此时无方案int x = sum + target >> 1;int[][] dp = new int[nums.length][x + 1];if(nums[0] <= x) dp[0][nums[0]] = 1;// 初始化最上行int numZero = 0;for(int i = 0; i < nums.length; i++) {// 初始化最左列if (nums[i] == 0) numZero++;dp[i][0] = (int)Math.pow(2.0, numZero);}for(int i = 1; i < nums.length; i++) {// 二维动规for(int j = 0; j <= x; j++) {if(j < nums[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i]];}}return dp[nums.length-1][x];}
}

一维版本

class Solution {int OFFSET = 1000;public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i = 0; i < nums.length; i++) {sum += nums[i];}if (sum < Math.abs(target)) return 0;// 即target的绝对值超过sum，此时无方案if ((sum + target) % 2 != 0) return 0;// 即正数和不为整数，此时无方案int bagSize = sum + target >> 1;int[] dp = new int[bagSize + 1];dp[0] = 1;//  符合为'-'时，无加数，和为0for(int i = 0; i < nums.length; i++) {for(int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
}

拓展：

如何确定递推公式呢？

只要知道nums[i]，那么使用nums[i]凑成j就有dp[j] = dp[j-nums[i]]种方法，最终把所有的dp[j-nums[i]]加起来，就能得到dp[j]。

所以，求组合数目的问题的公式，都形如：

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

1049.最后一块石头的重量Ⅱ（1049.最后一块石头的重量Ⅱ）

题目分析：

给定一堆石头，stones数组表示每块石头的重量。每次任意选出两块石头，它们的重量分别为x和y，且x <= y，那么当x == y，则两块石头一起粉碎；如果x < y，那么重量为x的石头粉碎，而重量为y的石头新重量为 y - x。

最后，至多只会剩下一块石头，返回此石头最小的可能重量。若无石头剩下，则返回0。

解题思路：

可以理解为将石头尽量分为重量相同的两堆（或差值最小的两堆），那么两堆相撞之后剩下的石头就是最小的。

动规五部曲：

1. 确定dp数组下标及其含义

1. 1. dp[j]表示容量为j的背包，所包含的子集的最大值

1. 确定递推公式：

1. 1. dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])

1. dp数组初始化：

1. 1. 数组中仅包含正整数，非0下标的元素初始化为0即可
   2. 题目中约定dp数组的长度不超过30，元素值不超过100，因此元素和的一般不超过1500，可以初始化dp数组的长度为1501

1. 确定遍历顺序：

1. 1. 先遍历物品，再从j = sum / 2（向下取整）开始倒序遍历背包（至j >= stones[i]）

1. 举例推导dp数组：

1. 1. 遍历完dp数组后，dp[target]表示这一堆石头的最大总重量，而sum - dp[target]表示另一堆石头的总重量，而后者一定大于等于前者，做差即为所求。

class Solution {public int lastStoneWeightII(int[] stones) {int[] dp = new int[1501];int sum = 0;for(int i = 0; i < stones.length; i++) {sum += stones[i];}int target = sum >> 1;// 向下取整，确保这一堆石头的总重量一定不大于另一堆石头的总重量for(int i = 0; i < stones.length; i++) {for(int j = target; j >= stones[i]; j--) {dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] * 2;}
}

474.一和零（474.一和零）

题目描述：

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

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

解题思路：

这道题不是多重背包，因为strs数组中的每一个元素就是物品，因此每个物品都只有一个，即同一个字符串中的0和1必须同时被放入背包或同时不放入背包。

而m和n相等于是一个背包的两个维度。

动规五部曲：

1. 确定dp数组以及下标的含义：

1. 1. dp[i][j]表示最多有i个0和j个1的背包所包含strs的最大子集的大小（即子集中的元素个数最多）为dp[i][j]。
   2. 实质上是一个二维背包的一维滚动数组

1. 确定递推公式：

1. 1. dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
   2. 此处，zeroNum和oneNum就是物品的重量，而字符串的个数就是其价值，体现在 +1 上。

1. dp数组初始化：

1. 1. 物品的价值即字符串的个数不为负数，那么只需初始化01背包的dp数组为0即可，使得递推的时候dp[i][j]不被覆盖

1. 确定遍历顺序：

1. 1. 外层循环物品，内层循环背包，倒序遍历。

1. 举例dp数组推导：省略。

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];for(String str : strs) {int zeroNum = 0;int oneNum = 0;for(int i = 0; i < str.length(); i++) {if(str.charAt(i) == '0') zeroNum++;else oneNum++;}for(int i = m; i >= zeroNum; i--) {for(int j = n; j >= oneNum; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}