每日一题 494目标和(0-1背包)(灵神笔记)
0-1背包模版
有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?
当前操作?枚举第i个物品选还是不选,不选容量不变,选容量减少
子问题?从前i个物品中的最大容量和
下一个子问题?不选:剩余容量为c,前i-1个物品中的最大容量和;选:
剩余容量为c-w[i],前i个物品中的最大容量和
public int dfs(int i, int c) {if (i < 0) {return 0;}if (c < w[i]) {return dfs(i - 1, c);}return dfs(n - 1, capacity);}
题目
目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 :
例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1:
输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2:
输入:nums = [1], target = 1
输出:1
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
题解
记忆化搜索
class Solution {private int[] nums;private int[][] cache;public int findTargetSumWays(int[] nums, int target) {// p 正数的和// s nums的和// target = p - (s - p)// p = (s + t)/2//题目转化为从nums选择数使他们恰好等于(s + t)/2// 其中(s+t)必须为偶数for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;this.nums = nums;int n = nums.length;cache = new int[n][target + 1];for (int i = 0; i < n ; i++) {Arrays.fill(cache[i],-1);}return dfs(n - 1,target);}public int dfs(int i, int c) {if (i < 0) {return c == 0 ? 1 : 0;}if (cache[i][c] != -1) {return cache[i][c];}if (c < nums[i]) {return cache[i][c] = dfs(i - 1, c);}return cache[i][c] = dfs(i - 1, c) + dfs(i - 1, c - nums[i]);}
}
递推
class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[][] f = new int[n+1][target+1];f[0][0] = 1;for (int i = 0; i < n; i++) {for (int c = 0; c <= target; c++) {if (c < nums[i]) {f[i+1][c] = f[i][c];} else {f[i+1][c] = f[i][c] + f[i][c-nums[i]];}}}return f[n][target];}
}
空间优化(两个数组)
class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[][] f = new int[2][target+1];f[0][0] = 1;for (int i = 0; i < n; i++) {for (int c = 0; c <= target; c++) {if (c < nums[i]) {f[(i+1)%2][c] = f[i%2][c];} else {f[(i+1)%2][c] = f[i%2][c] + f[i%2][c-nums[i]];}}}return f[n%2][target];}
}
空间优化(一个数组)
class Solution {public int findTargetSumWays(int[] nums, int target) {for (int x : nums) {target += x;}if (target < 0 || target % 2 == 1) {return 0;}target /= 2;int n = nums.length;int[] f = new int[target+1];f[0] = 1;for (int x : nums) {for (int c = target; c >= x; c--) {f[c] += f[c-x];}}return f[target];}
}