01背包和目标和问题转化DP

494 目标和转 0-1 背包

1. 前提条件

每个数有两种选择：
加正号：选到正号集合 P
加负号：选到负号集合 N

设：

所有数总和 = s
正号集合的和 = p
负号集合的和 = s - p

题目要求：正号和 - 负号和 = target

所以：
p - (s - p) = target

展开：
2p - s = target

所以：
p = (s + target) / 2
也就是转化成两个值不同情况的取舍问题
2. 什么情况下无解？

因为：
p = (s + target) / 2

所以必须满足：
s + target >= 0

并且：

(s + target) % 2 == 0

更完整地说：

如果 target > s 或 target < -s，也无解。

例如：

nums = [1,2,3]
s = 6
target = 10

最大也只能得到 6，不可能得到 10。

4. 为什么变成 0-1 背包？

原题是：每个数前面选 + 或 -

等价于：从 nums 里选一些数放进正号集合 P

要求：

选出来的数的和 = p

其中：

p = (s + target) / 2

所以变成：从数组中选一些数，使它们的和等于 p，问有多少种选法。

这就是 0-1 背包的计数版本的转化理解。

5. 和普通 0-1 背包的区别

普通 0-1 背包常见问法：容量不超过 capacity 时，最大价值是多少？

所以它是：最大值问题

转移用：max(...)

目标和这题问的是：

有多少种选法能刚好凑出 p？

所以它是：方案数问题

转移用：+
6. dp[j] 怎么理解？

定义：dp[j] 表示：从已经看过的数字里，凑出和 j 的方案数。

初始化：

dp[0] = 1;

意思是：什么都不选，凑出 0，有 1 种方案。

这点非常重要。

7. 转移怎么理解？

对于当前数：

x = nums[i]

要凑出 j，有两类方案：

1. 不选 x：
   原来 dp[j] 里的方案还在。

2. 选 x：
   那么之前必须先凑出 j - x。
   这些方案数量是 dp[j - x]。

所以dp[j] = dp[j] + dp[j - x];

也就是：

dp[j] += dp[j - x];

这就是“方案数相加”。

8. 为什么要倒序？

因为每个元素只能用一次。

for (int j = capacity; j >= x; j--) {
dp[j] += dp[j - x];
}

倒序可以保证：

dp[j - x] 还是上一轮的结果，
不会让当前 nums[i] 被重复使用。

如果正序，就会变成完全背包，当前元素可能被用多次。
也就是说本题把正负号两个情况转换成了01背包，正号集合和 = p，负号集合和 = s-p
则：p-(s-p)=target
推出：
p=(s+target)/2

问题转化：
从nums中选一些数
使其和为capacity
capacity=(s+target)/2
这样之后Dp数组里面总是有两种情况选x和不选x，这样就不断往前回溯，倒序是为了保证每次更新
dp[0]是默认什么都不选的情况，也就是空集，这种情况是默认为1，后续是选进来的情况加入集合，capacity作为选出符合要求dp的情况，其实默认就是选出正号集合的和
9. C 语言作答
#include <stdlib.h>

int findTargetSumWays(int* nums, int numsSize, int target) {
int s = 0;

for (int i = 0; i < numsSize; i++) {
    s += nums[i];
}

if (target > s || target < -s) {
    return 0;
}

if ((s + target) % 2 != 0) {
    return 0;
}

int capacity = (s + target) / 2;

int* dp = malloc((capacity + 1) * sizeof(int));

for (int j = 0; j <= capacity; j++) {
    dp[j] = 0;
}

dp[0] = 1;

for (int i = 0; i < numsSize; i++) {
    int x = nums[i];

    for (int j = capacity; j >= x; j--) {
        dp[j] += dp[j - x];
    }
}

int ans = dp[capacity];

free(dp);

return ans;

}
二、拿py理解一下

1. 先想递归
   class Solution:
   def findTargetSumWays(self, nums: List[int], target: int) -> int:
   s = sum(nums) - abs(target)
   if s < 0 or s % 2:
   return 0

    @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
    def dfs(i: int, c: int) -> int:
        if i < 0:
            return 1 if c == 0 else 0
        if c < nums[i]:
            return dfs(i - 1, c)  # 只能不选
        return dfs(i - 1, c) + dfs(i - 1, c - nums[i])  # 不选 + 选
   
    m = s // 2  # 背包容量
    return dfs(len(nums) - 1, m)
   

定义：dfs(i, sum)

表示：

处理到第 i 个数时，当前和是 sum，最后能凑成 target 的方案数。

对于 nums[i] 有两个选择。

选择一：加 +
dfs(i + 1, sum + nums[i])
选择二：加 -
dfs(i + 1, sum - nums[i])

所以：

dfs(i, sum)= dfs(i + 1, sum + nums[i])+ dfs(i + 1, sum - nums[i])

为什么是加？

因为题目问：

有多少种方案

所以左右两种选择的方案数要加起来。

3. 记忆化搜索：处理负数 sum

问题是：sum 可能是负数，不能直接当数组下标。

所以要加一个偏移量。

设：total = nums 所有元素之和

那么 sum 的范围是：

[-total, total]

可以用：

sum + total

把负数下标平移成非负数。

例如：

sum = -3
total = 10
index = sum + total = 7
5. 记忆化搜索 C 代码

这里用二维数组：

memo[i][sum + total]

表示：

处理到 i，当前和为 sum 时的方案数。
#include <stdlib.h>

int dfs(int* nums, int numsSize, int target, int i, int sum,
int total, int** memo) {
if (i == numsSize) {
if (sum == target) {
return 1;
} else {
return 0;
}
}

int index = sum + total;

if (memo[i][index] != -1) {
    return memo[i][index];
}

int add = dfs(nums, numsSize, target, i + 1, sum + nums[i], total, memo);
int sub = dfs(nums, numsSize, target, i + 1, sum - nums[i], total, memo);

memo[i][index] = add + sub;

return memo[i][index];

}

int findTargetSumWays(int* nums, int numsSize, int target) {
int total = 0;

for (int i = 0; i < numsSize; i++) {
    total += nums[i];
}

if (target > total || target < -total) {
    return 0;
}

int cols = 2 * total + 1;

int** memo = malloc(numsSize * sizeof(int*));

for (int i = 0; i < numsSize; i++) {
    memo[i] = malloc(cols * sizeof(int));

    for (int j = 0; j < cols; j++) {
        memo[i][j] = -1;
    }
}

int ans = dfs(nums, numsSize, target, 0, 0, total, memo);

for (int i = 0; i < numsSize; i++) {
    free(memo[i]);
}

free(memo);

return ans;

}

目标和易错点
易错点 1：方案数问题用加法

目标和问：

有多少种方案

所以转移是：

add + sub

或者：

dp[j] += dp[j - x]

不是 max。

易错点 2：target 可能是负数

如果用记忆化搜索，sum 可能为负数，要加偏移量。

sum + total
易错点 3：背包转换时要判断奇偶

如果：

target + total

是奇数，那么：

positive = (target + total) / 2

不是整数，直接返回 0。

易错点 4：背包容量是 positive或者定义的capacity

不是 target。

是：

positive = (target + total) / 2

494 目标和：
题型：
计数 DP / 01 背包方案数

递归定义：
dfs(i, sum)
表示处理到第 i 个数，当前和为 sum，最后凑成 target 的方案数。

递归转移：
dfs(i, sum)
= dfs(i + 1, sum + nums[i])
+ dfs(i + 1, sum - nums[i])

背包转换：
positive - negative = target
positive + negative = total

positive = (target + total) / 2

转换后：
从 nums 中选一些数，使和为 positive，求方案数。

背包状态：
dp[j] 表示凑出 j 的方案数。

转移：
dp[j] += dp[j - nums[i]]

遍历：
j 倒序。

目标和的本质是：每个数前面选 + 或 -，计数所有能到 target 的路径；也可以转成 01 背包的选数方案数。

题目 问什么 决策 转移核心
198 打家劫舍 最大收益 偷 / 不偷 max
494 目标和 方案数量 加正号 / 加负号 +