计数类dp防重复的核心是在状态定义时明确“最后一步”或“结尾特征”，如dpi或dpi，确保每种方案唯一对应一个状态格子，转移时满足互斥覆盖且初始化匹配语义。

计数类 DP 最容易在“子问题划分”和“状态定义”上出错，导致同一方案被多次计入。核心不是靠后期去重，而是在设计 dp 状态时就切断重复路径。

状态定义必须明确“最后一步”或“结尾特征”

重复计算往往源于状态含义模糊，比如只定义 dp[i] 为“前 i 个元素的合法方案数”，但没约束这些方案如何生成。正确做法是让状态携带构造过程的关键信息：

• dp[i] 改为 dp[i][last]：表示以第 last 个元素结尾、考虑前 i 个元素的方案数（如子序列计数）
• dp[i] 改为 dp[i][mod]：表示前 i 个数选完后，总和对某数取模为 mod 的方案数（避免不同组合产生相同余数却被合并）
• 对字符串子序列计数，常用 dp[i] 表示“以位置 i 结尾的子序列个数”，再用 last_occurrence 数组减掉之前已算过的同字符结尾方案

转移时必须保证“无后效性 + 互斥覆盖”

即使状态定义清晰，转移逻辑仍可能引入重复。关键看每种方案是否**恰好被一个状态且仅一次**捕获：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

• 错误示例：dp[i] = dp[i-1] + dp[i-2] 直接套用斐波那契形式——这适合求值，但不适用于计数，除非你能证明两类方案完全不重叠
• 正确思路：枚举“最后选哪个”，比如在“不相邻子集计数”中，dp[i] = dp[i-2] + dp[i-3] + ... 是错的；应拆成 dp[i] = dp[i-1] + dp[i-2]，其中 dp[i-1] 表示不选第 i 个，dp[i-2] 表示选第 i 个（则第 i-1 个必不选），二者互斥
• 若涉及字符/数字去重（如统计不含重复字符的子序列），必须记录每个字符上次出现位置，并在转移时减去 dp[prev_pos - 1]，否则 "a...a" 中两个 a 会各自触发相同前缀的重复计数

初始化和边界要匹配状态语义

状态含义变了，初始值就不能照搬斐波那契那一套。常见翻车点：

• 定义 dp[i][j] 为“前 i 个数中选若干个，和为 j 的方案数”，则 dp[0][0] = 1（空集和为 0），dp[0][j>0] = 0；若误设 dp[0][0] = 0，所有方案都会少算空集
• 定义 dp[i] 为“以第 i 个元素结尾的上升子序列个数”，则 dp[i] 初始为 1（单个元素本身），不是 0；否则所有长度为 1 的子序列都被漏掉
• 模运算下做减法必须加 mod 再取模，例如 (dp[i] - prev) % mod 应写成 (dp[i] - prev + mod) % mod，否则负数取模结果异常，间接导致计数错乱

真正难的不是写转移方程，而是想清楚“每个合法方案，在整个 DP 表里，它唯一落脚的那个格子是哪一个”。一旦这个映射关系不唯一，重复就不可避免——而且这种 bug 往往只在小数据上不暴露，到 n=1000 才突然多出几倍答案。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！