计数类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会各自触发相同前缀的重复计数
初始化和边界要匹配状态语义
状态含义变了，初始值就不能照搬斐波那契那一套。常见翻车点：
立即学习“C++免费学习笔记（深入）”；
- 定义
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 才突然多出几倍答案。
