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 case
if (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整数数组默认初始值为0
if (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];
}
}本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！