每日一题 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];}
}