动态规划（DP）分类

• Catalan 数的组合意义
• DP 递推 C_n = Σ C_i·C_{n-1-i}
• 组合公式 C_n = C(2n,n)/(n+1)

Catalan 数 C_n 计数多种等价结构：n 对合法括号序列数、n 个节点的二叉树个数、n 个元素出栈序列数等。DP 递推：C_0=1，C_n = Σ_{i=0}^{n-1} C_i·C_{n-1-i}，即把解按"第一个元素/根的分割"分解为两个独立子问题（如括号序列的第一个匹配括号把序列分成 i 对外加 n-1-i 对，二叉树按根左右子树划分）。组合公式：C_n = C(2n,n)/(n+1) = (2n)!/((n+1)!·n!)，可由反射原理推导（把合法括号序列与所有序列做差）。两种方式等价，DP 递推 O(n²) 适合中等规模，组合公式 O(n)（用阶乘与逆元）适合大规模。

Catalan 数的本质是"用递归分解计数"：任何合法的 Catalan 结构都可以按第一个"根"分割成两个独立子结构，从而得到卷积递推。组合公式是递推的闭式解，两者给出计算上的灵活性。

• 回文子串的区间 DP 定义
• 转移方程与边界处理
• 复杂度 O(n²)

定义 dp[i][j] 表示子串 s[i..j] 是否为回文。转移：若 s[i]==s[j]，则 s[i..j] 是回文当且仅当 s[i+1..j-1] 是回文；若长度 ≤ 2（j-i<3，即长度 1 或 2），只要两端相等就是回文，无需依赖内部。因此 dp[i][j] = (s[i]==s[j]) && (j-i<3 || dp[i+1][j-1])。边界 j-i<3 覆盖了长度 1（单字符，本身回文）和长度 2（两端相等即回文）这两种内部子串越界或未定义的情形，避免 dp[i+1][j-1] 在 i+1>j-1 时越界。最后统计所有 dp[i][j]==true 的数量即为回文子串总数。按区间长度从小到大枚举，复杂度 O(n²)。

区间 DP 的转移依赖"去掉两端后的内部子串"，因此必须按区间长度递增枚举，保证内部子串已算。j-i<3 是边界条件，它把"长度 1 和 2"这两个最小情形直接由两端相等判定，既避免越界又保证正确性。

• tails 数组的定义与不变性
• 二分查找定位与替换
• 替换不改变长度的正确性

维护一个递增数组 tails，其中 tails[k] 表示"长度为 k 的递增子序列的最小末尾值"。遍历原数组时，对每个元素 x，用二分查找在 tails 中找到第一个 ≥ x 的位置 pos：若 pos == len，则说明 x 可以接在某个长度 len 的子序列后形成更长的递增序列，把 x 追加到尾部（len++）；否则在用 x 替换 tails[pos]（因为 x 比当前 tails[pos] 小，作为该长度的更小末尾值更优）。替换不会改变长度，因为 tails 长度只代表"最长递增子序列的长度"，替换只是把某些长度的末尾值改小，不减少已得到的长度，也不影响"存在长度为 len 的递增子序列"这一事实。最终 tails 的长度就是 LIS 长度。每个元素二分 O(log n)，总 O(n log n)。

tails 数组保持"递增性"是该解法的核心：二分查找保证插入位置精确。替换的合理性在于"更小的末尾值只会让后续扩展更容易"，不会破坏已有长度或递减 tails 的单调性，因此长度正确性保持不变。

• 矩阵链乘的区间 DP 定义
• 递推式与分割点 k
• 维度数组 p 的来源

矩阵链乘问题：n 个矩阵 A_1..A_n 连乘，求最少的标量乘法次数。设 m[i,j] 为计算 A_i..A_j 的最少乘法次数。递推：m[i,j] = min_{k=i}^{j-1} { m[i,k] + m[k+1,j] + p_{i-1}·p_k·p_j }，基准 m[i,i]=0。其中最后一项 p_{i-1}·p_k·p_j 是合并 A_i..A_k 与 A_{k+1}..A_j 两个结果矩阵所需的乘法数。维度数组 p：A_i 的维度是 p_{i-1}×p_i（p 有 n+1 个元素），因为 A_i 有 p_{i-1} 行、p_i 列，合并时 A_i..A_k 的维度是 p_{i-1}×p_k，A_{k+1}..A_j 是 p_k×p_j，相乘需要 p_{i-1}·p_k·p_j 次乘法。按区间长度递增枚举，对每个区间枚举分割点 k，总复杂度 O(n³)。

矩阵链乘是典型区间 DP：把"整体乘法"按最后一个外层分割点 k 拆成两个独立子问题，子问题合并的代价是 p_{i-1}·p_k·p_j。p 数组编码了所有矩阵的维度信息，是合并代价的核心来源。

• 树上背包的 DP 定义
• 合并子树时容量倒序枚举的原因
• 复杂度优化（背包合并的 bound）

树上背包：每个节点是一个物品，选择子树时需枚举容量。dp[u][j] 表示以 u 为根的子树中选择 j 个容量（或 j 个物品）的最优值。合并 u 的子树 v 时，枚举 u 侧已用的容量 j 和 v 侧的分给容量 k，有 dp[u][j+k] = max(dp[u][j+k], dp[u][j] + dp[v][k])。这里 j 必须倒序枚举（从大到小），因为 dp[u][j] 在同一轮中会被更新，正序会使用"本层已更新过的值"导致重复使用子树 v 的物品（类似 0-1 背包的倒序）。复杂度优化：合并时容量上界用"当前已处理子树大小"限制，而不是始终到 m，即遍历 j ≤ 当前子树大小、k ≤ v 子树大小，这样总复杂度从 O(n·m²) 降到 O(n·m)（每对节点只在 LCA 处合并一次，总合并次数 O(n·m) 上界，实际为 O(n·m) 到 O(n·m²) 之间，常用树上背包优化为 O(n·m)）。

倒序枚举保证"同一子树 v 的物品不重复使用"，这是 0-1 背包性质在树上的体现。复杂度优化本质是"合并时只枚举实际存在的容量范围"，避免对每个节点都枚举到 m，从而把合并复杂度与子树大小绑定。

• 多重背包的二进制拆分
• 单调队列优化背包
• 容量维度枚举的去除

多重背包：每种物品有数量限制 c。二进制拆分：把 c 个同种物品拆成 1,2,4,...,2^k 及剩余 r 个，转化为 0-1 背包，复杂度 O(n·m·log c)。单调队列优化：0-1/完全背包的转移 dp[j] = max(dp[j], dp[j-w]+v) 具有"按余数 j mod w 分组的滑动窗口最大值"结构。对每种物品，按容量对 w 取模分组，每组内用单调队列维护窗口内 dp 的最大值，从而 O(1) 摊还完成该组所有容量的转移，去掉内层"枚举数量 k"的循环。这样每种物品的容量转移从 O(m·c) 降到 O(m)，总复杂度 O(n·m)。

单调队列优化的关键在于转移的"距离约束"（数量上限 c）构成固定窗口，可以用单调队列求窗口最大值。它把"枚举用几个该物品"的 O(c) 压缩为单调队列的 O(1) 摊还，从而去掉容量维度的一层枚举。二进制拆分是另一种更简单但 O(log c) 的替代。

• 三维 DP 状态的定义
• k 的含义（左侧连续相同盒子数）
• 引入额外维度的原因

移除盒子：移除连续的相同颜色盒子得分为长度²，求最大得分。若只定义 dp[l][r]（移除 l..r 内盒子的最大得分），转移会丢失"左侧有 k 个与盒子 l 同色且连在一起的盒子"这一信息，因为当移除盒子 l 时，它与左侧 k 个同色盒子合并会带来 (k+1)² 的额外收益。因此定义 dp[l][r][k] 表示"当移除 l..r 时，盒子 l 左侧已有 k 个与它同色且连续的盒子"的最大得分。转移：要么直接移除盒子 l 及左侧 k 个（得分 (k+1)² + dp[l+1][r][0]），要么把 l 与右侧某个同色盒子 last 一起移除（先移除 l+1..last-1 得 dp[l+1][last-1][0]，再把 l 与 last 合并，状态变为 dp[last][r][k+1]）。引入 k 维度是因为"多个同色盒子组合时得分是长度²，不是线性"，必须知道左侧合并数量才能正确计算。

得分是长度²导致"合并数量"非线性，丢失 k 信息会低估收益。三维状态 dp[l][r][k] 显式记录左侧合并数量，使转移能正确计算合并收益。这是"状态空间不足需扩展维度"的典型。

• 按位统计的思路
• 当前位三种情况（0/1/大于1）的贡献公式
• O(log N) 复杂度

统计 [0,N] 中所有数字里数字 '1' 出现的总次数，按每一位独立统计贡献。考虑第 i 位（从右往左，权重 10^i），设 high = N / 10^(i+1)，cur = (N / 10^i) % 10，low = N % 10^i。该位 '1' 的贡献分三种情况：1）cur == 0：贡献 = high × 10^i（高位从 0 到 high-1，低位 10^i 种组合）；2）cur == 1：贡献 = high × 10^i + (low + 1)（高位到 high 时低位取 0..low）；3）cur > 1：贡献 = (high + 1) × 10^i（高位取 0..high 均含，低位 10^i 种）。把所有位的贡献相加即得总次数，每位 O(1)，共 O(log N) 位，总复杂度 O(log N)。

按位统计把"整体计数"分解为"每一位贡献"，通过对 cur 的三种情况分别处理高位与低位的组合数，避免枚举。这是数位统计的经典技巧，O(log N) 远优于枚举。

• 滚动数组的空间优化
• 0-1 背包倒序枚举的原因
• 正序枚举的错误

0-1 背包 DP 用 dp[j] 表示容量 j 的最大价值，转移 dp[j] = max(dp[j], dp[j-w]+v)。若只需一维数组，必须倒序枚举 j（从大到小）：因为 dp[j-w] 是"上一轮"（未使用当前物品）的值，倒序时 dp[j-w] 还没被本轮更新（j-w < j，倒序时先处理 j 大、后处理 j 小，所以 dp[j-w] 仍是旧值），保证每个物品只被使用一次。若正序枚举，dp[j-w] 可能已被本轮更新（包含当前物品），导致同一物品被重复使用，变成完全背包的语义，结果错误。因此 0-1 背包第二维倒序，完全背包正序。

倒序/正序的本质是控制"当前物品是否可重复使用"。0-1 背包要求每个物品至多一次，需用旧值 dp[j-w]，故倒序；完全背包允许无限次，用新值，故正序。滚动数组只省空间，不改变转移语义。

• Stirling 数第二类的定义
• 递推式的组合意义
• 边界条件

Stirling 数第二类 S(n,k) 表示把 n 个不同的元素划分成 k 个非空子集的方案数。递推式 S(n,k)=k·S(n-1,k)+S(n-1,k-1) 的组合意义：考虑第 n 个元素，它要么单独成为一个新子集，此时其余 n-1 个元素划分成 k-1 个非空子集，方案数 S(n-1,k-1)；要么加入已有的某个子集，此时其余 n-1 个元素划分成 k 个非空子集，第 n 个元素可加入这 k 个子集中的任意一个，方案数 k·S(n-1,k)。两部分相加即得递推。边界 S(n,0)=0（n>0）、S(0,0)=1、S(n,n)=1、S(n,1)=1。DP 递推 O(n·k) 计算。

递推式是"按第 n 个元素的归属"分类：新开子集或并入已有子集。这是组合计数"对最后一个元素分类讨论"的典型，两部分互斥且完备，给出递推。

• 区间 DP 与分治的关系
• 最优二叉搜索树的递推
• 重复子问题与记忆化

区间 DP 与分治法都把问题按"中间分割点"分解为子问题（如最优二叉搜索树选根 k 分为左右子树），但分治法的递归分解会产生大量重复子问题：不同分割路径会反复计算相同区间。最优二叉搜索树：dp[i][j] = min_k { dp[i][k-1] + dp[k+1][j] + sum_{t=i}^{j} w[t] }，W 是各节点权重和。若用分治递归，同一区间 (i,j) 会被多次计算；DP 用表格记录每个区间的最优值，按区间长度递增枚举，每个区间只算一次，避免重复。DP 本质是"带记忆的分治"：它保存子问题结果，消除重复计算。最优二叉搜索树 DP 复杂度 O(n³)，优于朴素递归的指数级。

分治与 DP 的共性都是"分解子问题"，差异在于 DP 显式保存并复用子问题结果。最优二叉搜索树的区间结构使其天然适合 DP，用表格避免分治的重复子问题。

• 递增数字的组合计数
• 组合数 C(9+k,k) 的推导
• 位数的组合

统计 [1,N] 中各位数字严格递增（每一位 > 前一位，且不含 0 作为首位）的整数个数。若只考虑 k 位数字且严格递增，本质是从 1-9 中选 k 个不重复数字按升序排列，方案数 C(9,k)。若要统计所有 k ≤ K 位（k 从 1 到 K）的递增数，则对不同 k 求和。当 N 很大（如 10^9，即最多 9 位）时，总数 = Σ_{k=1}^{9} C(9,k)。若考虑"非严格递增"或允许前导 0 的变体，会引入 C(9+k,k) 之类的可重复组合形式（从 10 个数字中选 k 个可重复的组合数 C(10+k-1,k) = C(9+k,k)）。严格递增不可重复时用 C(9,k)，含可重复的变体用 C(9+k,k)（可重复组合）。对 N 的部分位数限制则需数位 DP 处理上限。

递增数字的计数可转化为"组合选择"问题：严格递增=从 1-9 选 k 个不可重复，非严格/可重复=隔板法 C(9+k,k)。组合转换把计数从枚举变为公式，需注意 N 的位数上限与可重复性。

• 区间 DP 的基准初始化
• 长度 1、2 的初始值
• 初始化错误的连锁影响

区间 DP 通常以最小长度区间为基准：dp[i][i]（长度 1）通常为 0（无需合并）或直接值，dp[i][i+1]（长度 2）按问题语义给定（如合并代价、最优值）。因为区间 DP 按长度递增枚举，长度大的区间依赖长度小的区间，若长度 1、2 的基准值错误，所有更大的区间都会基于错误值递推，导致整个 DP 结果错误。例如石子合并 dp[i][i]=0，dp[i][i+1]=w[i][i+1]；若 dp[i][i] 误设为非 0，长度 2 的区间就错了，进而污染所有长度。初始化是"递归基"，必须正确。

DP 的基准（base case）是递推的起点，错误基准会通过依赖链传播到所有状态。区间 DP 的基准是长度 1（和长度 2）的区间，必须按问题语义精确设置。

• 区间 DP 状态定义 dp[l][r]
• 一般转移形式
• 区间长度递增枚举的原因

区间 DP 的状态 dp[l][r] 表示处理子区间 [l,r] 的某个最优值/方案数。一般转移形式为 dp[l][r] = opt_{k 在 l、r 之间} { combine(dp[l][k], dp[k+1][r] 或 dp[k][r]) } + 该区间的合并代价，其中 k 是分割点，opt 是 min 或 max。因为转移依赖"更小的区间"（l..k 与 k+1..r 等，长度都小于 [l,r]），所以必须按区间长度从小到大枚举：先算长度 1、2 的区间，再算长度 3、4，保证转移时依赖的子区间已算好。若不按长度递增，则可能引用尚未计算的较大区间。

区间 DP 的依赖关系是"由小到大"的（子区间更短），按长度递增枚举确保每个区间的依赖都先于它完成。这是区间 DP 的枚举顺序核心，也保证时间复杂度 O(n³) 或 O(n²)。

• 戳气球问题的反向建模
• 区间 DP 的状态定义
• 转移方程与得分

戳气球问题：依次戳破气球，得分 = 气球与其左右相邻未戳破气球值的乘积。正向"戳破"难以建模，因为边界气球会变化。反向建模：把"戳破"反过来视为"按顺序添加气球"。设 dp[l][r] 表示在区间 (l,r) 内（不含端点 l、r）添加气球能获得的最大得分，其中 l、r 是边界气球（始终存在）。转移：枚举区间内最后添加的气球 k，则 dp[l][r] = max_k { dp[l][k] + dp[k][r] + nums[l]·nums[k]·nums[r] }。因为 k 是最后添加的，此时 l、k、r 都未被戳破，得分 nums[l]·nums[k]·nums[r]，加上左右两侧子区间 dp[l][k]、dp[k][r]。反向建模使"最后添加"的气球成为合并点，边界固定，状态清晰。

反向"添加"把"端点变化"的戳破问题转化为"边界固定"的区间合并问题，最后一个添加的气球对应合并点 k，得分由两端点决定。这是区间 DP 的经典建模技巧。

• 数位 DP 的状态组成
• 状态数与转移数的乘积
• 复杂度上界估算

数位 DP 的状态由 (pos, state, limit, lead) 组成：pos 是当前处理到第几位（0 到位数 d，d ≤ log10 N），state 是问题相关的状态（可能为 0 或某数），limit 表示是否受到上界约束（2 种），lead 表示是否有前导零（2 种）。时间复杂度 = 状态数 × 转移数 ≈ d × |state| × 2 × 2 × 转移分支数。转移分支是当前位可选的数字（0-9 或受 limit 限制），最多 10 种。因此上界约为 O(d × |state| × 4 × 10) = O(d·|state|·40)，其中 d = O(log N)。由于记忆化，每个状态只计算一次，总复杂度即状态数 × 转移数，通常远小于枚举 N 个数的 O(N)。

数位 DP 的复杂度由"状态空间大小"决定，limit 和 lead 各贡献 2 倍，pos 是位数，state 是问题维度。记忆化保证每个状态一次，调用的转移最多 10 次，故上界为 O(logN · |state| · 40)，比 O(N) 枚举大幅改善。

• 状压 DP 的状态定义
• 转移方程
• 复杂度 O(2^n·n²)

TSP 求经过所有城市一次并回到起点的最短路径。状态 dp[mask][v] 表示"已访问的城市集合为 mask，且当前停在城市 v 的最短路径长度"。转移：从 v 出发枚举下一个未访问城市 u，dp[mask|1<<u][u] = min(dp[mask|1<<u][u], dp[mask][v] + dist[v][u])。复杂度：mask 有 2^n 种，v 有 n 种，共 O(n·2^n) 个状态；每个状态枚举 u（n 种）转移，总 O(n²·2^n)。这是精确 TSP 的标准 DP 解，空间 O(n·2^n)。相比暴力枚举 n! 种排列，状压 DP 的 2^n 大幅降低复杂度。

状态用位掩码 mask 表示"访问集合"，用 v 表示"当前位置"，两者结合完整描述子问题。转移枚举下一城市，每个状态 O(n) 转移，总 O(n²·2^n)。这是"状态压缩"把排列枚举降为集合 DP 的典型。

• 石子合并的区间 DP
• 四边形不等式（决策单调性）
• s[i][j] 单调性与 O(n²) 优化

石子合并 dp[i][j] = min_{k∈[i,j)} { dp[i][k] + dp[k+1][j] } + sum[i][j]，直接 O(n³)。若代价函数满足四边形不等式（sum 为四边形不等式：sum[a][c]+sum[b][d] ≤ sum[a][d]+sum[b][c] 对 a≤b≤c≤d），则最优分割点 s[i][j] 满足决策单调性：s[i][j-1] ≤ s[i][j] ≤ s[i+1][j]。于是枚举 k 时只需在 [s[i][j-1], s[i+1][j]] 范围内找，分摊后每个状态 O(1) 摊还，总复杂度 O(n²)。证明思路：利用四边形不等式与区间合并的单调性，通过"最优决策点随区间右端右移而右移、随左端右移而左移"（决策单调性）证明 s[i][j] 的单调夹逼关系，从而缩小枚举范围。

四边形不等式优化（Knuth 优化）的核心是"决策单调性"：最优分割点随区间增大而单调移动。s[i][j-1] ≤ s[i][j] ≤ s[i+1][j] 使每个状态的枚举范围从 O(n) 摊还到 O(1)，把 O(n³) 降为 O(n²)。

• 状压 DP 的规模限制
• 子集枚举优化
• 预处理转移表

状压 DP 的状态数为 2^n，n 通常 ≤ 20（2^20 ≈ 100 万，状态可接受），n ≤ 25 时已很紧张（2^25 ≈ 3300 万）。在此规模下，常数优化才值得。常见优化：1）子集枚举优化：需要枚举 mask 的所有子集时，用"for (sub = mask; sub; sub = (sub-1)&mask)"直接枚举真子集，复杂度 3^n 而非 4^n，适合需要"子集划分"的 DP（如最小覆盖/分成若干组）；2）预处理转移表：把相邻状态间的转移（如 cost[mask][u]）或 bit 运算结果预计算，避免 DP 内重复计算，减少常数。当 n > 25 时，2^n 状态已不可行，此时应改用其他算法（如分支定界、启发式、近似），而非优化常数。

状压 DP 的瓶颈是指数级状态数，只有 n 足够小（≤20 左右）才可行。优化（子集枚举、预处理）解决的是常数与 3^n vs 4^n 的差距，在 n 大时依然无法突破指数本身。

• 贪心安全的条件（最优子结构 + 贪心选择性质）
• 构造反例证明贪心错误
• DP 的适用场景

贪心安全需要满足"贪心选择性质"（局部最优能导出全局最优）和"最优子结构"（子问题最优解构成整体最优解）。若能证明每一步贪心选择都在某个最优解中，则贪心正确（如活动选择、哈夫曼、Dijkstra）。若贪心选择会破坏后续最优性，则贪心错误。构造反例：找一个"当前贪心选择最优但后续需要次优选择才能达到全局最优"的实例。例如部分背包 vs 0-1 背包：0-1 背包按单位价值贪心选会错（因为物品不可分割，选单位价值最高可能占用容量导致整体差），反例是"高单位价值但占满容量"的物品 vs 几个低单位价值但合计价值更高的物品。此时局部最优（单位价值）不导出全局最优，需用 DP。贪心错误即存在反例，证明贪心错误只需构造一个反例。

贪心与 DP 的边界在于"局部最优是否必然全局最优"。有反例说明贪心不可靠，则该问题需 DP（或更精确的算法）。判断贪心正确与否，要么证明贪心选择性质，要么找反例。

• 自底向上（bottom-up）与自顶向下（top-down）DP
• 钢条切割与矩阵链乘的 DP 实现
• 两种方式的工程语义与取舍

自顶向下（记忆化）DP：从原问题递归求解，先检查子问题是否已算过，未算则递归计算并缓存，即"递归 + 备忘录"。自底向上 DP：按子问题规模从小到大递推，先算小子问题再组合成大问题，通常用循环 + 表格。钢条切割：r[n] = max_{1≤i≤n} { p[i] + r[n-i] }，自顶向下用递归带 memo，自底向上按长度递增填 r[]。矩阵链乘：m[i][j] 按区间长度递增填。工程语义：自顶向下更符合"只算需要的子问题"（适合稀疏子问题、跳过无效状态），代码直观、易实现；自底向上无递归开销、可控性高、适合所有子问题几乎都会被用到的情况。两者复杂度相同，只是计算顺序不同。

两种 DP 计算的是同一组子问题，只是"求解顺序"不同：自顶向下按需递归+缓存，自底向上按规模递增。工程上自顶向下实现简单、可跳过无效状态，自底向上更高效、无栈溢出风险，选型取决于子问题密度与实现偏好。

• 区间 DP 与记忆化搜索的等价性
• 记忆化搜索跳过无效状态
• 稀疏状态 vs 稠密状态的取舍

区间 DP 与记忆化搜索（递归 + 缓存）求解的是同一组子问题，递推关系相同，只是枚举顺序不同：区间 DP 按长度递增遍历所有区间，记忆化搜索只递归访问实际需要的子区间。二者等价，复杂度依赖一致。记忆化搜索能自动跳过无效状态：当 DP 表格中大量状态是"非法/不会用到"的（如某些区间在问题中不出现），记忆化搜索只在递归中被实际调用时才计算并缓存，不会遍历所有状态；而自底向上区间 DP 会无条件计算每个区间。因此在状态稀疏（大量无效状态）时，记忆化搜索更快；状态稠密（几乎所有区间都用）时二者相当，自底向上可能更省调用开销。

等价性在于"同一递推、同一子问题集合"。记忆化搜索的优势是"按需计算"，它天然跳过无效/不可达状态，适合状态稀疏的场景；自底向上适合状态稠密、需要稳定遍历的场景。

• limit 与 lead 在状态中的作用
• 去掉 limit 的多计数问题
• 去掉 lead 的漏计数问题

limit 表示当前位是否受到上界 N 的约束（之前各位是否都贴着 N 的上界）。若去掉 limit，会把"贴着上界"与"自由"的状态混为一谈，导致把超过 N 的数也计入，产生多计数。例如统计 [0,N] 中某属性个数，若某位之前已贴着 N，当前位不能超过 N 的对应位，去掉 limit 会错误地允许超过 N，多计数。lead 表示是否有前导零（当前是否还在填写前导零）。若去掉 lead，会把"前导零"当作真正的数字 0 参与统计，导致漏计或误计。例如统计"不含连续 1"的整数，若前导零被当作 0，则 "0011" 这类前导零后的 1 会被误判为"出现连续 1"，漏掉合法的数；或统计"数字中 0 的个数"时误把前导零计入。因此 limit 与 lead 都必须作为状态（记忆化参数），否则统计错误。

limit 控制"不超过上界"的合法性，lead 控制"前导零是否算数位"的语义。两者都会改变可选数字集合与统计口径，不纳入状态会污染共享的记忆化结果，导致多计数或漏计数。

• 背包 DP 的统一状态定义
• 各变体的转移差异
• "容量-物品"框架

背包类问题统一为"物品-容量"框架：状态 dp[j] 表示容量为 j 时的最优值（或方案数），按物品顺序转移。0-1 背包：每个物品至多选一次，倒序枚举容量 dp[j]=max(dp[j], dp[j-w]+v)。完全背包：每个物品无限次，正序枚举容量 dp[j]=max(dp[j], dp[j-w]+v)。分组背包：把物品分成若干组，每组最多选一个，先枚举组、再倒序枚举容量、组内枚举选哪个物品。三者都统一在"容量 j 存最优值、按物品（或组）逐个转移"的框架下，差异仅在枚举顺序（倒序/正序）与物品粒度（单个/组）。

背包问题的共性是把"容量"作为状态维度、按"物品"递推。0-1 用倒序保证不重复，完全用正序允许重复，分组在组内、组间做两层选择。理解这个框架即可套用各种背包变体。

• 区间 DP 的典型套路
• 先枚举区间长度的原因
• 复杂度

区间 DP 的典型套路：dp[l][r] 表示区间 [l,r] 的最优值，先枚举区间长度 len（从 1 到 n），再枚举左端点 l（r = l+len-1），最后枚举分割点 k 做转移。如合并石子按长度递增枚举区间，回文分割按长度递增枚举并判断回文。先枚举区间长度是因为转移依赖更短的子区间（dp[l][k]、dp[k+1][r] 长度都小于当前区间），按长度递增保证依赖的子区间已先算好。若先枚举端点而混用长度，可能引用未计算的区间。复杂度通常 O(n³)（枚举长度×端点×分割点）或 O(n²)（无分割点枚举）。

区间 DP 的依赖是"由短到长"，先枚举长度是保证依赖顺序的编程习惯。套路是"长度→左端点→分割点"三层循环，配合正确的初始化，可求解合并、分割、区间最优等一类问题。

• 数位 DP 的 state 用位掩码
• 不重复数字的统计
• 状态压缩的实现

数位 DP 中，当状态需要记录"已使用的数字集合"（如统计各位数字不重复的整数个数）时，state 用位掩码（bitmask）表示：用一个 int 的 10 位（对应数字 0-9）标记哪些数字已被使用。例如统计 [1,N] 中各位数字都不重复的整数个数，dp[pos][mask][limit][lead] 中 mask 的第 d 位表示数字 d 是否已用过；转移时若当前位数字 d 使 mask 的第 d 位为 1 则跳过（重复），否则置位并继续。状态压缩把"集合"编码为整数，使状态可哈希、可作记忆化键，空间从枚举集合缩小到 2^10 种 mask。这是数位 DP 处理"集合类状态"的标准技巧。

位掩码把"已用数字集合"压缩成单个整数状态，使记忆化可行。mask 的每个位对应一个元素的存在性，转移时用位运算检查/置位，是"状态压缩"最直接的应用。

• 前缀计数 f(N) 与差分
• 转化为 f(R)-f(L-1) 的原因
• L=0 的边界处理

数位 DP 通常只实现"求 [0,N] 内满足性质的整数个数"f(N)（因为数位 DP 处理上界 N 方便）。要求 [L,R] 内的个数，用差分 f(R)-f(L-1)：因为 [L,R] 内个数 = [0,R] 内个数 - [0,L-1] 内个数，避免为每个区间单独实现带下界约束的 DP。L=0 时，f(L-1)=f(-1) 无意义，此时 [0,R] 内个数就是 f(R)，直接返回 f(R)（或令 f(-1)=0）。若 L=0 且问题统计 0 本身，需按 f 的定义决定是否包含 0（通常 f(N) 含 0，则 [0,R] 用 f(R)）。一般处理：L==0 时结果 = f(R)，否则 = f(R)-f(L-1)。

数位 DP 天然适合"上界计数"，用前缀差分把"区间计数"拆成两个前缀计数，避免实现下界约束。L=0 时 f(L-1) 越界，需特判直接返回 f(R)。

• 记忆化搜索的四参数
• 各参数的含义
• 不含连续 1 的示例

数位 DP 记忆化搜索框架参数：pos（当前处理到第几位，从高位到低位）、state（与数位性质相关的状态）、limit（当前位是否受上界 N 约束）、lead（是否有前导零）。以统计 [1,N] 中不含连续 1 的整数个数为例：用 dfs(pos, state, limit, lead) 递归，state 记录上一位是否为 1（0/1，用于判断是否出现连续 1）。转移时枚举当前位数字 d：若 limit 则 d 不能超过 N 的对应位；若 lead 且 d=0 则保持前导零（state 不变）；若 state==1 且 d==1 则出现连续 1，跳过。递归到 pos==长度 时若 lead 为真（非全零）返回 1。limit 与 lead 参数在记忆化时需区分（只有 limit=false 且 lead=false 的普通状态可缓存），避免污染。

四参数完整描述数位 DP 状态：pos 定位、state 携带数位性质、limit 处理上界、lead 处理前导零。记忆化时只缓存"不受 limit 约束"的通用状态，保证正确性。不含连续 1 用 state 表示上一位是否 1。

• isNum 与 limit 参数
• 记忆化键的选取
• 避免状态爆炸

数位 DP 记忆化参数中，limit 表示是否受上界约束，isNum（或 lead）表示是否已开始填非前导零数字（isNum=true 表示已开始真正的数位）。设计原则：记忆化缓存只对"不受 limit 约束"且"已脱离前导零"的状态进行（即 limit=false 且 isNum=true 的通用状态），因为 limit=true 的状态受具体上界影响，不能复用；isNum=false 的前导零状态也需单独处理。这样记忆化键通常是 (pos, state, isNum)，limit 不作为缓存键（limit=true 直接计算不缓存）。避免状态爆炸：1）只缓存 limit=false 的状态，把 limit 从缓存键剔除；2）state 用紧凑表示（位掩码/小整数）；3）isNum 用布尔区分。这样状态数 = 位数 × |state| × 2，远小于枚举所有数。

状态爆炸源于不必要的缓存维度。limit 使状态依赖具体上界，不能复用，故剔除出缓存键；isNum 只需 2 态。合理设计缓存键（pos, state, isNum）把状态数控制在 O(位数 × |state|)，避免爆炸。

• 换根法的适用场景
• 换根的核心思想
• 正确性证明

换根法（rerooting）适用于这样的树形 DP：需要以每个节点为根求得某个答案（如"以每个节点为根的子树大小之和""每个节点到所有其他节点的距离和""每个节点作为根的最优方案"），且一次 DFS 只能求一个根。换根法先以任意根（如 1）做一次 DFS 计算出"向下"信息（每个节点以其为根、只考虑子树内的贡献），再做一次 DFS 做"换根"：从根转移到其邻接子节点时，用父节点的答案减去子节点子树的贡献、加上子节点作为新根所需的其他贡献，O(1) 更新子节点的答案。因为树是无环的，换根只影响父子关系，且每个节点的答案 = 向下信息 + 来自父方向的信息，可通过"父答案减去子贡献 + 补偿"递推，枚举所有根只需两次 DFS，总 O(n)。正确性证明：对任意节点 u，以其为根的答案可分解为"子树内贡献"与"父方向贡献"两部分，向下 DFS 给出子树内贡献，换根 DFS 从根出发依次依托父亲答案正确推导出每个节点的父方向贡献，归纳证明每个节点答案正确。

换根法的适用条件是"答案可分解为子树内与父方向两部分，且换根时父方向可 O(1) 由父节点答案推出"。正确性由"从根出发的换根 DFS 保证每个节点在推导时父节点答案已正确"（归纳）保证，从而两次 DFS 得到所有根的答案。