夸父追日：第九章动态规划part04

今日收获：最后一块石头的重量 II，目标和，一和零

1. 最后一块石头的重量 II

题目链接：1049. 最后一块石头的重量 II - 力扣（LeetCode）

思路：将石头分为重量相近的两堆。本题可以转化为01背包问题，容量为综合一半的背包中能放入的最大石头重量，石头的花费和价值都为重量值。

方法：

class Solution {public int lastStoneWeightII(int[] stones) {// 让分开的两堆石头尽可能总和相近// 容量为总和一半的背包最多能装多少// 计算数组总和，确定背包最大容量int sum=0;int len=stones.length;for (int i=0;i<len;i++){sum+=stones[i];}int target=sum/2;int[] dp=new int[target+1];for (int i=0;i<len;i++){for (int j=target;j>=0;j--){if (j>=stones[i]){dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);}}}return sum-dp[target]*2;}
}

总结：

（1）这道题和416. 分割等和子集 - 力扣（LeetCode）思路很像，只是对于最后取得的最大值的处理不同。

（2）01背包问题可以求特定容量下的最大值问题，应用的时候需要转化为01背包问题。

2. 目标和

题目链接：494. 目标和 - 力扣（LeetCode）

思路：

（1）本题需要经过数学推导才能转化为背包问题，add-sub=target，add+sub=sum，add=（target+sum）/2。

（2）前几题都是求容量最大时的最大值，这题是求容量为目标值时装满有几种方法。

（3）如果是二维的dp数组：

dp[i][j]表示背包容量为j时，遍历到第i个物品时装满背包的方法。
递推公式是当前容量下装满背包的方法=不用物品 i 时的方法数（上一行同一列）+上一行留出物品 i 的容量时装满背包的方法数（此时再加物品 i 就可以装满背包）
初始化dp二维数组的第一行和第一列，因为要从上一行推出当前位置。第一行要先判断物品0的容量是否小于等于背包容量，如果是则只有一个位置能装满，否则全部初始化为0。第一列初始化时要累加值为0的元素个数，因为0元素可以添加正/负号来装满容量为0的背包
遍历顺序：一层层从左到右

方法：

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum=0;for (int i=0;i<nums.length;i++){sum+=nums[i];}if (Math.abs(target)>sum){  // 无法求得目标和return 0;}if ((sum+target)%2==1){return 0; // 小数，背包无法装满}int bag=(sum+target)/2;int[][] dp=new int[nums.length][bag+1];// 初始化if (nums[0]<=bag){dp[0][nums[0]]=1;}int zero=0;for (int i=0;i<nums.length;i++){// 0可以取正负两种情况if (nums[i]==0){zero++;}dp[i][0]=(int)Math.pow(2,zero);}for (int i=1;i<nums.length;i++){for (int j=1;j<bag+1;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][bag];}
}

3. 一和零

题目链接：474. 一和零 - 力扣（LeetCode）

思路：本题的背包是二维的（需要满足两个维度的容量限制），字符串相当于物品，需要先遍历物品再倒序遍历背包。

dp数组定义：dp二维数组表示背包的容量为 i，j 时的最大子集个数。
初始化：dp数组可以全部初始化为0
递推公式：用不用当前的字符串，不用就是原来的值，用的话需要用空出来当前字符串0和1数量位置的最大子集个数再加1
遍历顺序：先遍历物品，再倒序遍历二维的背包，类似于之前一维背包问题的一维数组解法。

方法：

class Solution {public int findMaxForm(String[] strs, int m, int n) {// 定义二维的dp数组背包，元素表示容量为i，j时的最大子集长度int[][] dp=new int[m+1][n+1];// 先遍历物品，背包倒序遍历for (String str:strs){int zero=0;int one=0;for (int i=0;i<str.length();i++){if (str.charAt(i)=='0'){zero++;}else {one++;}}for (int i=m;i>=0;i--){for (int j=n;j>=0;j--){if (i>=zero&&j>=one){dp[i][j]=Math.max(dp[i][j],dp[i-zero][j-one]+1);}else {dp[i][j]=dp[i][j];}}}}return dp[m][n];}
}

总结：第一次碰到二维背包问题，需要先遍历物品再倒序遍历背包（类似于一维背包的一维dp数组解法）：

（1）如果先便利背包再遍历物品，则导致背包中只能放一件物品

（2）如果正序遍历背包，可能会导致一个物品被放入多次。