target sum solution
来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum
Ray_Lee_HZ
2022-09-24
Hi bobo老师,
对于494. Target Sum 这道题目，我使用了记忆化搜索的形式解决了，并且accepted, 但是想不出怎么用dp来解决，能给一些思路么？
下面是我的记忆化搜索的方法：
class Solution {
class Pair {
int index;
int target;
public Pair(int index, int target) {
this.index = index;
this.target = target;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Pair pair = (Pair) o;
return index == pair.index && target == pair.target;
}
@Override
public int hashCode() {
return Objects.hash(index, target);
}
}
public int findTargetSumWays(int[] nums, int target) {
if (nums.length == 0){
return 0;
}
// use memory to save the method consider from index i to sum the target
Map<Pair,Integer> memory = new HashMap<>();
return ways(nums, 0 , target , memory);
}
public int ways(int[] nums, int index, int target, Map<Pair,Integer> memory){
if (index == nums.length -1){
int res = 0;
if (target == nums[index]){
res++;
}
if (target == -nums[index]){
res++;
}
return res;
}
Pair pair = new Pair(index,target);
if (memory.get(pair) != null){
return memory.get(pair);
}
int result = 0;
Pair pair1 = new Pair(index + 1, target - nums[index]);
Pair pair2 = new Pair(index + 1, target + nums[index]);
if (memory.get(pair1) != null){
result = result + memory.get(pair1);
} else {
int a = ways(nums , index + 1 , target - nums[index] , memory);
memory.put(pair1 , a);
result = result + a;
}
if (memory.get(pair2) != null){
result = result + memory.get(pair2);
} else {
int b = ways(nums , index + 1 , target + nums[index] , memory);
memory.put(pair2, b);
result = result + b;
}
return result;
}
}
1回答
-
liuyubobobo
2022-09-24
整体思路是：
dp[i][s] 表示的是：使用 i 个数字，可以构成和为 s 的方案数。(注意，i 是使用的数字个数，而不是 nums 的索引)。
则最终结果为 dp[n][target]。
状态转移是：
dp[i][s] = dp[i - 1][s - nums[i - 1]] + dp[i - 1][s + nums[i - 1]]
即：使用 i 个数字，可以构成和为 s 的方案数，可以由两种方式组成：
第一种方式：使用 i - 1 个数字构成 s - nums[i - 1]，然后在第 i 个数字，为 nums[i - 1] 赋上正号（第 i 个数字的索引是 i - 1）
即：(s - nums[i - 1]) + nums[i - 1] = s
第一种方式：使用 i - 1 个数字构成 s + nums[i - 1]，然后在第 i 个数字，为 nums[i - 1] 赋上负号。
即 (s + nums[i - 1]) - nums[i - 1] = s
初始：dp[0][0] = 1，其余 dp[0][x] = 0。即使用 0 个数字，只有一种方案构成 0。
在下面的具体实现上，有一个小“技巧”。
在这个问题中，s 可能是负数，所以不能直接用 s 做索引。我们需要把 s “平移成”正数。
假设 nums 中所有数字加在一起是 sum，则 nums 中的数字可以组成的数字范围是 [-sum, sum] （一共 2 * sum + 1 种可能。）
我们给每一个 s 加上一个 sum，就能保证其在正数范围。
即：[-sum, sum] + sum = [0, 2 * sum]。这样一来，任何一个 s 对应的实际索引，是 s + sum。（在下面的代码中，我叫 offset，表示偏移量。）
更具体可以参考下面的代码和注释：
class Solution { public int findTargetSumWays(int[] nums, int target) { int sum = 0; for(int num: nums) sum += num; // 如果 target 不在 [-sum, sum] 的范围，肯定得不到 target，直接返回 0 if(target < -sum || target > sum) return 0; int n = nums.length; int[][] dp = new int[n + 1][2 * sum + 1]; // 这里注意 dp 的空间大小，第一维度的范围是 [0, n]，所以大小是 n + 1 // 第二维度承载 [-sum, sum] 之间的所有可能，所以大小是 [0, 2 * sum + 1] int offset = sum; dp[0][0 + offset] = 1; // 初始 0 个数字只能构成 0。注意在第二个维度，实际的和要加上偏移量 // 所以是 dp[0][0 + offset] = 1 // dp 过程 for(int i = 1; i <= n; i ++){ for(int s = -sum; s <= sum; s ++){ // 求解 dp[i][s + offset]，依然是，要加 偏移量 // s 可能来自 i - 1 个数字构成 s + nums[i - 1] 或者 s - nums[i - 1] 两种可能 // 注意实际实现的时候，要判数组是否越界 if(-sum <= s + nums[i - 1] && s + nums[i - 1] <= sum) dp[i][s + offset] += dp[i - 1][s + nums[i - 1] + offset]; if(-sum <= s - nums[i - 1] && s - nums[i - 1] <= sum) dp[i][s + offset] += dp[i - 1][s - nums[i - 1] + offset]; } } // 最终结果是 dp[n][target + offset]，依然是，不要忘了偏移量 return dp[n][target + offset]; } }==========
另外，非常重要的，这个问题的 n 最大为 20，所以枚举所有的加符号的可能，只有 2^20 = 100w 种可能。这个数据规模是不会超时。强烈建议试试看。
继续加油！：）
10
相似问题