目标和

最直接的想法：每个数独立选 + 或 −，n 个数就是 2ⁿ 种符号组合，逐一算结果看是否等于 target。数一多就指数爆炸，而且大量子和被重复计算。

记取 + 的数之和为 P、取 − 的为 N。两式联立：P＋N=sum、P−N=target，解得 P=(sum+target)÷2。问题就变成：选一个子集，使它的和恰好等于 P，有几种选法——这正是 0-1 背包计数！状态 dp[j]=凑出和 j 的方法数，转移 dp[j]+=dp[j−x]。这里 P=(5+3)÷2=4。

建表 · dp[0]=1：表头是子集和 0 到 4。dp[j] 记「选出的数之和恰好为 j 的方法数」。dp[0]=1（空集就能凑出 0，算一种），其余先为 0。目标看 dp[4]。

放第 1 个 1：放第一个 1，内层从大到小扫：dp[1] += dp[0] = 1。意思是「用这一个 1 凑出和 1」有 1 种方法。其余格暂时凑不出，仍是 0。

放第 1 个 1 · 装不下的格：注意负例：容量 0 这格想装数字 1，j−1 会变成负数，根本装不下。所以循环只扫到 x 为止，dp[0] 永远沿用「这个数不选」的旧值 1。这保证了空集这一种方法不被破坏。

放第 2 个 1：放第二个 1：dp[2] 累加上 dp[1] 得 1，dp[1] 再累加 dp[0] 变成 2。每个 dp[j] 都把「上一个数填好的 dp[j−1]」叠进来，方法数开始往上长。

放第 3 个 1：放第三个 1：dp[3] 第一次有值（=dp[2]=1），dp[2] 累加到 3，dp[1] 累加到 3。数值排成 [1,3,3,1]，正是杨辉三角的一行。

放第 4 个 1：放第四个 1：dp[4] 终于被点亮（=dp[3]=1），整行变 [1,4,6,4,1]。每一格仍是「左边一格的旧值」叠加上来，杨辉三角继续生长。

放第 5 个 1：放最后一个 1：dp[4] += dp[3]，由 1 累加成 5。整行 [1,5,10,10,5] 是杨辉三角第 5 行。看目标列 dp[4]。

答案 = dp[P]：子集和恰好为 P=4 的选法有 dp[4] = 5 种——对应「让 4 个数取正、1 个取负」的 5 种挑法，这就是答案。

遇到「给每个数选 +/− 凑 target」，一律转成「选子集和恰好为 (sum+target)÷2」的背包计数。一个数学变形，就把看着唬人的符号题打回经典模型。

迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

边界三连：边界三连：极端输入先过一遍。

几个高频追问，记住答法。