题目描述
每个数前面放 + 或 −，使表达式结果等于 target，求方法数。
nums = [1, 1, 1, 1, 1]
target = 3
输出 = 5
思路解析
记取正号的数之和为 P、取负的为 N。P+N=sum、P−N=target，解得 P=(sum+target)/2。问题变成：选一个子集，和恰好为 P，有几种选法——0-1 背包计数！这里 P=(5+3)/2=4。
建表 · dp[0]=1：dp[j] 表示选出子集和为 j 的方法数。dp[0]=1，空集凑出 0。目标看 dp[4]。
放入第 1 个 1：放入第一个 1，从大到小更新：dp[1] += dp[0] = 1。能凑出和 1 的方法有 1 种。
放入第 2 个 1：第二个 1：dp[2]=1、dp[1]=2。数值开始像杨辉三角一样长了。
放完 5 个 1：把 5 个 1 都放完，dp = [1,5,10,10,5]，正好是杨辉三角第 5 行。看 dp[4] = 5。
答案 = dp[P]：子集和为 P=4 的选法有 5 种，这就是答案。
遇到「给每个数选 +/− 凑 target」，一律转成「选子集和为 (sum+target)/2」的背包计数。一个数学变形就把难题打回经典模型。
参考代码（Python）
Python
1s = sum(nums)
2if (s + target) % 2 or s < abs(target): return 0 # 无解
3P = (s + target) // 2
4dp = [0] * (P + 1); dp[0] = 1
5for num in nums:
6 for j in range(P, num - 1, -1): # 0-1 从大到小
7 dp[j] += dp[j - num]
8return dp[P]复杂度分析
- 时间复杂度：O(n × P) —— n 个数 × 目标和
- 空间复杂度：O(P) —— 一维 dp
套路模板
记住骨架：dp[0]=1、内层从大到小、dp[j]+=dp[j−x]。关键往往是「先把题目变形成子集和」这一步。
Python
1dp = [0]*(W+1); dp[0] = 1 # 计数初值 1
2for x in items:
3 for j in range(W, x - 1, -1): # 从大到小=每物一次
4 dp[j] += dp[j - x] # 累加方案数
5return dp[W]易错点
- ❌ 不判 (sum+target) 的奇偶/范围 → ✅ 为奇数或越界直接返回 0（P 必须是非负整数才有解）
- ❌ 内层从小到大 → ✅ 0-1 背包从大到小（每个数只能用一次）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。