力扣爆刷第74天–动态规划
一、494.目标和
题目链接：https://leetcode.cn/problems/target-sum/description/
思路：求目标和的组合数，把物品里的元素分为左右两堆，left+right=sum，left-right=target，两式相加可以得到left = (sum + target)/2，那么题目就转变成了，从物品中挑选元素把容量为left的背包填满有多少种元素组合，这求的是组合数，定义dp[j]表示，把容量为j的背包填满有dp[j]种方法。每一个元素可以选择加入也可以选择不加入，不加入nums[i]有dp[j]种方法填满j容量，加入nums[i]有dp[j-nums[i]]种方法填满j容量，故递推公式为dp[j] += dp[j-nums[i]]。
class Solution {
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;
if((sum + target) % 2!= 0) return 0;
int left = Math.abs((sum + target) / 2);
int[] dp = new int[left+1];
dp[0] = 1;
for(int i = 0; i < nums.length; i++) {
for(int j = left; j >= nums[i]; j--) {
dp[j] += dp[j-nums[i]];
}
}
return dp[left];
}
}
二、474.一和零
题目链接：https://leetcode.cn/problems/ones-and-zeroes/description/
思路：一和零求符合m个0和n个1的元素的个数，其实就是背包可放入元素的最大数量，背包有两个维度而已，是二重背包，和0,1背包的做法是一样的。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for(String str: strs) {
int a = 0, b = 0;
for(char c: str.toCharArray()) {
if(c == '0') a++;
else b++;
}
for(int i = m; i >= a; i--) {
for(int j = n; j >= b; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i-a][j-b] + 1);
}
}
}
return dp[m][n];
}
}
