本文主要是介绍day43 动态规划part05，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1049.最后一块石头的重量II
与昨天的分割等和子集其实是同样的题
分为两堆后，要求差值最小，其实就是分堆最大，并且范围是[0,sum/2]
This question eaquals to partition an array into 2 subsets whose difference is minimal
(1) S1 + S2 = S
(2) S1 - S2 = diff
==> -> diff = S - 2 * S2 ==> minimize diff equals to maximize S2
Now we should find the maximum of S2 , range from 0 to S / 2, using dp can solve this
494.目标和
其实可以用回溯算法，但是单纯的回溯算法超时了，所以要用记忆化回溯
class Solution {int findTargetSumWays(int[] nums, int target) {if (nums.length == 0) return 0;return dp(nums, 0, target);}// 备忘录HashMap<String, Integer> memo = new HashMap<>();int dp(int[] nums, int i, int remain) {// base caseif (i == nums.length) {if (remain == 0) return 1;return 0;}// 把它俩转成字符串才能作为哈希表的键String key = i + "," + remain;// 避免重复计算if (memo.containsKey(key)) {return memo.get(key);}// 还是穷举int result = dp(nums, i + 1, remain - nums[i]) + dp(nums, i + 1, remain + nums[i]);// 记入备忘录memo.put(key, result);return result;}
}空间复杂度很大
还可以简化为动态规划问题
首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：
sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)
综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2
先理解二维规划，再换成一维
1 dp 定义
dp[i][j] = x 表示，若只在前 i 个物品中选择，若当前背包的容量为 j，则最多有 x 种方法可以恰好装满背包。
2 递推公式：
回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么恰好装满背包的方法数就取决于上一个状态 dp[i-1][j]，继承之前的结果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么只要看前 i - 1 个物品有几种方法可以装满 j - nums[i-1] 的重量就行了，所以取决于状态 dp[i-1][j-nums[i-1]]。
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];3 初始化
根据这个定义，显然 dp[0][..] = 0，因为没有物品的话，根本没办法装背包；但是 dp[0][0] 应该是个例外，因为如果背包的最大载重为 0，「什么都不装」也算是一种装法，即 dp[0][0] = 1。
Note
可能有些看过前文 0-1 背包问题 和 完全背包问题 这两篇背包问题的文章之后会有疑问，为什么 base case 不是 dp[..][0] = 1 呢？即背包容量为 0 时，只有「什么都不装」这一种装法。这里不能这样初始化，是因为本题 nums 数组中的元素是可能为 0 的，那么背包容量为 0 时，「什么都不装」可能就不是唯一的装法了，而需要在状态转移的过程中具体去计算。
注意dp[0][0] 对于i=0时相当于没物品，整个dp数组大小是dp[n+1][Sum+1]; i=1的时候才相当于加入了第一个物品
4.对于二维的动归：外围循环是物品/空间都可以；
class Solution {public int findTargetSumWays(int[] nums, int target) {// 01背包应用之“有多少种不同的填满背包最大容量的方法“// 易于理解的二维数组解法及详细注释int sum = 0;for(int i = 0; i < nums.length; i++) {sum += nums[i];}// 注意nums[i] >= 0的题目条件，意味着sum也是所有nums[i]的绝对值之和// 这里保证了sum + target一定是大于等于零的，也就是left大于等于零（毕竟我们定义left大于right）if(sum < Math.abs(target)){return 0;}// 利用二元一次方程组将left用target和sum表示出来（替换掉right组合），详见代码随想录对此题的分析// 如果所求的left数组和为小数，则作为整数数组的nums里的任何元素自然是没有办法凑出这个小数的if((sum + target) % 2 != 0) {return 0;}int left = (sum + target) / 2;// dp[i][j]：遍历到数组第i个数时， left为j时的能装满背包的方法总数int[][] dp = new int[nums.length][left + 1];// 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1// 其他情况dp[0][j] = 0// java整数数组默认初始值为0if (nums[0] <= left) {dp[0][nums[0]] = 1;}// 初始化最左列（dp[i][0])// 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案// n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）int numZeros = 0;for(int i = 0; i < nums.length; i++) {if(nums[i] == 0) {numZeros++;}dp[i][0] = (int) Math.pow(2, numZeros);}// 递推公式分析：// 当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数// nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]// 由递推公式可知，先遍历i或j都可for(int i = 1; i < nums.length; i++) {for(int j = 1; j <= left; j++) {if(nums[i] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];}}}// 打印dp数组// for(int i = 0; i < nums.length; i++) {// for(int j = 0; j <= left; j++) {// System.out.print(dp[i][j] + " ");// }// System.out.println("");// }return dp[nums.length - 1][left];}
}转化为1维时：
1. 确定dp数组以及下标的含义
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
2.状态转移公式：
dp[j] = dp[j]+dp[j-nums[i-1]] //i是由1开始的。（把上一层的数据储存在数组中，滚动更新）
3. 初始化
dp[0]=1;
但是dp[0]可能在过程中状态转移中更新，其实对应dp[0][.....]。因为本题比较特殊物品的大小是有可能为0的
4. 遍历顺序：01背包的一维dp 必须物品在外循环，空间在内循环，且在内循环上倒序
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int num: nums){sum+=num;}if((target+sum)%2!=0)return 0;int sumA = (target+sum)/2;// if ( target < 0 && sum < -target) return 0;if(Math.abs(target)>sum)return 0;int[] dp = new int[sumA+1];dp[0]=1;for(int i=0;i<nums.length;i++){for(int j=sumA;j>=0;j--){if(j>=nums[i]){dp[j]=dp[j]+dp[j-nums[i]];}else dp[j] = dp[j];}}return dp[sumA];}
}如果sumA不为整数，说明这个子集就不存在，可以直接返回为0
if((target+sum)%2!=0)return 0;
如果target绝对值大于sum说明不可能存在答案，return0
尤其
如果target<0且sum<-target；如果不直接返回的话，sumA<0，生成dp数组时会报错
另一种情况target>0 且target >sum，仍然可以执行程序 dp[sumA]=0;不会影响结果
474.一和零
本题其实就是01背包但是背包空间有两个维度
如果不压缩，其实应该是三维的dp数组
1. 确定dp数组（dp table）以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2. 确定递推公式
两个状态如果用这个物体，就是 dp[i][x][y]=dp[i-1][x-zeroNum][y-oneNum]+1
如果不用的话就是 dp[i][x][y]=dp[i-1][x][y]
选最大的。
压缩为2维后就是
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
其实物体的价值就是物体的数量
3. 初始化
因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖
（此题并不是有多少种情况，还是类似最大价值）
4. 遍历顺序
先遍历物体
再遍历空间 倒序遍历，由于空间是2维所以倒序遍历x，y，总共三个循环
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] count01 = new int[strs.length][2];for(int i=0;i<strs.length;i++){for(char c: strs[i].toCharArray()){if(c=='0')count01[i][0]++;else count01[i][1]++;}}int[][] dp = new int[m+1][n+1];dp[0][0] = 0;for(int i=0;i<strs.length;i++){for(int x = m;x>=count01[i][0];x--){for(int y = n;y>=count01[i][1];y--){dp[x][y] = Math.max(dp[x][y],dp[x-count01[i][0]][y-count01[i][1]]+1);}}}return dp[m][n];}
}这篇关于day43 动态规划part05的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
