数据结构与算法 / 系统课时
统计恰好达到目标的方案数
统计恰好达到目标的方案数
这一类题不再问“最大能装多少价值”,而是问有多少种选择能让总和恰好等于目标。关键变化只有一个:状态保存的是方案数量,dp[0] = 1 表示空集合构成零和的一种方案,它是所有后续计数能够产生的起点。
学习目标
- 用一维动态规划表示“恰好凑出某个和”的方案数
- 理解
dp[0] = 1为什么不是特殊补丁,而是计数转移的必要初值 - 正确处理不可达目标、重复物品与零值物品的边界
把状态改成方案数量
以“每个整数最多选择一次”为例,设 dp[s] 表示处理到当前物品后,恰好得到总和 s 的方案数。读到一个值 x 时,如果某个旧方案能得到 s - x,那么把 x 加进这个方案,就会得到一个新的和为 s 的方案,因此转移是:
dp[s] += dp[s - x]
这里保存的不是最优值,而是所有合法来源的数量之和。如果目标值从来没有被任何转移到达,dp[target] 会自然保持为 0,这正好表达“零种方案”。
为什么空集合必须记为一种方案
初始化时只有 dp[0] = 1,其他位置都是 0。这个 1 表示“什么都不选”恰好得到总和 0 的一种方式。
假设第一个数是 2。更新 dp[2] 时会读取 dp[0]。如果 dp[0] 被初始化为 0,就意味着连“从空集合加入 2”这一条最基本的路径都不存在,之后所有状态也都会继续是 0。
因此计数型动态规划中,dp[0] = 1 是递推的单位元:它不是说空集合达到了非零目标,而是给第一批合法方案提供来源。
用倒序保证每个物品只选一次
对于 0/1 选择,容量必须从目标值向 x 倒序遍历。这样当前物品产生的新状态不会在同一轮再次被读取,从而避免同一个物品被重复使用。
下面统计数组 [1, 2, 3, 4] 中有多少个子集的元素和恰好为 5:
def count_exact_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for x in nums:
# 倒序更新,确保当前元素在这一轮最多使用一次。
for s in range(target, x - 1, -1):
dp[s] += dp[s - x]
return dp[target]
print(count_exact_subsets([1, 2, 3, 4], 5))预期输出
2两种方案分别对应 {1, 4} 和 {2, 3}。如果把容量改成从小到大遍历,刚写入的 dp[s] 可能再次参与当前轮转移,语义就会从“每个物品最多一次”变成“当前物品可以重复使用”。
识别几个计数边界
当 target = 0 时,若题目把“什么都不选”视为合法方案,答案就是 1。如果业务语义明确要求至少选择一个物品,则需要在最终答案处额外排除空集合,而不是破坏 dp[0] = 1 这个递推基础。
当所有物品都是正整数且目标不可达时,不需要特殊判断,结果自然为 0。若输入允许值为 0,每个零值物品都可以“选或不选”而不改变总和,因此会让已有方案数翻倍;这是否符合题意必须提前确认。
若数组中出现相同数值,还要区分“物品按位置是否不同”。例如两个独立物品都等于 3,它们通常是两个可分别选择的对象;如果题目只关心数值集合而不区分来源,则应先去重或改用与题意一致的建模方式。
计数题最重要的不是把求最大值的 max 换成加法,而是先确认状态代表什么方案、每个物品能用几次、相同选择是否被视为同一种方案。这三个语义确定后,初始化和遍历方向才有唯一正确的写法。