# 1. Catalan 数计数（合法括号序列/二叉树个数/出栈序列）如何用 DP 递推 C_n = Σ C_i·C_{n-1-i} 与组合公式 C_n = C(2n,n)/(n+1) 两种方式计算 A C_n 同时计数合法括号序列、二叉树个数、出栈序列，递推为 C_n = Σ C_i·C_{n-1-i}，也可用组合公式 C(2n,n)/(n+1) ✓ 正确答案 B C_n 递推是 C_n = C_{n-1} + C_{n-2} C Catalan 数与二叉树无关 D Catalan 数只能用组合公式，无法用 DP 递推
# 2. 回文子串计数（LeetCode 647）如何用区间 DP 在 O(n²) 完成？dp[i][j]=(s[i]==s[j]) && (j-i<3 || dp[i+1][j-1]) 的边界为何是 j-i<3 A 转移不依赖内部子串，无需考虑边界 B 回文子串计数必须用 O(n³) 才能完成 C 长度 2 的子串即使两端不等也是回文 D 边界 j-i<3 覆盖长度 1、2 的子串，避免内部越界，区间 DP 总复杂度 O(n²) ✓ 正确答案
# 3. LIS 的 O(n log n) 解法中维护递增数组并二分替换的原理，为什么替换不影响长度正确性？ A 替换会破坏已得到的长度，导致结果错误 B tails 数组无需保持单调递增 C 该方法只能求 LIS 长度，无法证明正确性 D tails[k] 存长度为 k 的递增子序列的最小末尾值，替换不改变长度，总复杂度 O(n log n) ✓ 正确答案
# 4. 矩阵链乘问题如何用区间 DP 在 O(n³) 求解？给出递推式 m[i,j]=min{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j} 并解释维度 p 的来源 A 递推 m[i,j]=min{ m[i,k]+m[k+1,j]+p_{i-1}p_kp_j }，p 是各矩阵维度，复杂度 O(n³) ✓ 正确答案 B 合并代价 p_{i-1}p_kp_j 与矩阵维度无关 C 矩阵链乘只需 O(n²) 时间 D 矩阵链乘用贪心即可，无需 DP
# 5. 树上背包中树形 DP 中合并子树的容量枚举为何要倒序，复杂度 O(n·m^2) 如何优化？ A 合并子树容量应正序枚举 B 合并子树时容量倒序枚举，避免重复使用同一子树物品，复杂度可优化到 O(n·m) ✓ 正确答案 C 树上背包与 0-1 背包无关 D 树上背包复杂度无法优化，必为 O(n·m²)
# 6. 多重背包的二进制拆分与单调队列优化中为什么单调队列能去掉容量维度的一层枚举？ A 单调队列按容量对 w 取模分组，用滑动窗口最大值 O(1) 完成转移，复杂度降到 O(n·m) ✓ 正确答案 B 单调队列优化与数量限制无关 C 多重背包无法优化，必为 O(n·m·c) D 二进制拆分把物品数拆成任意数量，复杂度 O(n·m)
# 7. 移除盒子（LeetCode 546）的 dp[l][r][k] 三维状态中 k 的含义是什么？为何需要引入额外维度 A dp[l][r] 二维状态足够，无需额外维度 B k 表示右侧连续同色盒子数量 C dp[l][r][k] 中 k 表示盒子 l 左侧连续同色盒子的数量，因得分是长度²需记录合并数量 ✓ 正确答案 D 移除盒子得分是线性的，无需合并信息
# 8. 统计 [0,N] 中数字'1'出现的总次数（LeetCode 233）中按位枚举当前位为 0/1/>1 三种情况，给出每位贡献的 O(log N) 公式 A 必须枚举 [0,N] 每个数字，O(N) B 按位统计，当前位为 0/1/大于 1 三种情况分别给出贡献公式，总复杂度 O(log N) ✓ 正确答案 C 只能统计最高位，无法统计所有位 D 当前位为 1 时贡献恒为 high × 10^i
# 9. 滚动数组的空间优化中背包 DP 第二维要倒序枚举，正序枚举会怎样？ A 0-1 背包第二维倒序枚举，保证每个物品只使用一次；正序会变成完全背包语义 ✓ 正确答案 B 滚动数组会改变转移语义 C 完全背包需倒序枚举 D 0-1 背包应正序枚举才能得到正确结果
# 10. Stirling 数第二类 S(n,k) 的 DP 递推式 S(n,k)=k·S(n-1,k)+S(n-1,k-1) 的组合意义 A S(n,k) 表示 n 个不同元素划分成 k 个非空子集的方案数，递推为 k·S(n-1,k)+S(n-1,k-1) ✓ 正确答案 B 递推中的第 n 个元素只能单独成子集 C S(n,k) 与划分无关，是排列数 D S(n,k) 表示 n 个元素排列成 k 个排列的方案数
# 11. 区间 DP 与分治法的联系中以最优二叉搜索树为例，说明 DP 如何避免分治的重复子问题 A 区间 DP 不保存子问题，仍会重复计算 B 区间 DP 与分治完全相同，都重复计算子问题 C 最优二叉搜索树只能用贪心求解 D 区间 DP 保存子问题结果，避免分治重复计算相同区间，最优二叉搜索树用 O(n³) DP 求解 ✓ 正确答案
# 12. 计数 DP 与组合计数结合中统计 [1,N] 中各位数字递增的整数个数，如何转化为组合数 C(9+k, k) 的求和 A 递增数字个数只能用枚举，无法组合计数 B 严格递增的 k 位数字相当于从 1-9 选 k 个不可重复，组合求和；可重复变体用 C(9+k,k) ✓ 正确答案 C 严格递增的三位数个数是 C(10,3) D 递增数字与组合数无关
# 13. 区间 DP 的常见初始化方式中 dp[i][i]=0、dp[i][i+1]=...，为何初始化错误会导致整个 DP 失效 A 初始化错误只影响长度 1 的区间 B 长度 1、2 的基准值错误会通过依赖链传播，导致整个 DP 失效 ✓ 正确答案 C 区间 DP 无需初始化长度 1 的子问题 D 长度 2 的区间与长度 1 无关，初始化不会影响
# 14. 区间 DP 的状态定义 dp[l][r] 与转移方程一般形式是什么？为何通常按区间长度从小到大枚举 A 区间长度递增枚举会算错依赖 B 区间 DP 应从大到小枚举，先算大区间 C 枚举顺序与依赖无关，任意顺序均可 D 转移依赖更小的子区间，故按区间长度从小到大枚举 ✓ 正确答案
# 15. 戳气球（LeetCode 312）的区间 DP 建模中为何要'反过来'把戳破视为添加，dp[l][r]=max{dp[l][k]+dp[k][r]+nums[l]*nums[k]*nums[r]} A 转移得分与端点无关 B 正向"戳破"建模最简单，无需反向 C 反向建模为"添加气球"，dp[l][r]=max{ dp[l][k]+dp[k][r]+nums[l]*nums[k]*nums[r] } ✓ 正确答案 D 戳气球问题不能用区间 DP 求解
# 16. 数位 DP 的时间复杂度 = 状态数 × 转移数，估算 pos(≤logN) × state × 2(limit) × 2(lead) 的上界 A limit 只贡献 1 倍状态，lead 无影响 B 数位 DP 复杂度是 O(N)，需枚举每个数 C 复杂度 ≈ 状态数 × 转移数，上界约 O(logN · |state| · 40)，因记忆化每个状态只算一次 ✓ 正确答案 D 转移分支最多 1 种
# 17. 状压 DP 求解 TSP 中为什么状态定义为 dp[mask][v]（已访问集合 mask 且当前在 v），转移枚举下一城市的复杂度 O(2^n·n²)？ A 状压 DP 复杂度是 O(n!) B TSP 状态只需 dp[v]，无需记录访问集合 C 状态 dp[mask][v]，mask 是已访问集合、v 是当前城市，复杂度 O(n²·2^n) ✓ 正确答案 D 转移枚举下一城市每状态 O(1)
# 18. 石子合并（相邻合并）的 O(n³) 区间 DP 如何用四边形不等式优化到 O(n²)？给出 s[i][j] 单调性的证明思路 A 四边形不等式优化让复杂度变为 O(n³) B 四边形不等式优化需要枚举所有 k，复杂度不变 C 石子合并无法用四边形不等式优化 D 代价满足四边形不等式时，最优分割点 s[i][j] 满足 s[i][j-1]≤s[i][j]≤s[i+1][j]，可优化到 O(n²) ✓ 正确答案
# 19. 状压 DP 的常见优化（子集枚举、预处理转移表）在什么数据规模下才值得使用？ A 子集枚举优化用 sub=(sub-1)&mask 枚举真子集，复杂度 3^n 而非 4^n，适合 n≤20 的规模 ✓ 正确答案 B 状压 DP 优化能让 n=30 也可行 C 预处理转移表只影响正确性，不影响性能 D 状压 DP 不受 n 限制，任何规模都可
# 20. DP 与贪心的边界中什么时候贪心是安全的，如何构造反例证明贪心错误？ A 0-1 背包按单位价值贪心总是正确 B 贪心总是安全的，无需任何条件 C 贪心安全需满足贪心选择性质与最优子结构，构造反例可证明贪心错误 ✓ 正确答案 D 反例只能证明 DP 错误，不能证明贪心错误
# 21. CLRS 第 15 章钢条切割与矩阵链乘法的自底向上与自顶向下 DP 的工程语义？ A 自顶向下比自底向上复杂度高 B 自顶向下是递归+缓存、按需计算，自底向上按规模递增递推，两者复杂度相同 ✓ 正确答案 C 自底向上无法求解钢条切割 D 自顶向下只能用于矩阵链乘
# 22. 区间 DP 与记忆化搜索（递归+缓存）的等价性中什么场景下记忆化搜索能自动跳过无效状态从而更快 A 二者求解同一子问题集合，等价；记忆化搜索按需计算，能自动跳过无效状态 ✓ 正确答案 B 记忆化搜索复杂度高于区间 DP C 记忆化搜索不能对区间 DP 状态缓存 D 区间 DP 也能跳过无效状态，与记忆化搜索无差别
# 23. limit（上界约束）与 lead（前导零）标记为何必须纳入状态？举例说明去掉 limit 会多计数、去掉 lead 会漏计数的情况 A limit 防止超过上界多计数，lead 防止前导零被误算导致漏计数，两者必须纳入状态 ✓ 正确答案 B limit 和 lead 可选，去掉不影响正确性 C 去掉 limit 会漏计数，去掉 lead 会多计数 D limit 只影响性能，不影响正确性
# 24. 背包类问题的状态设计中 0-1 背包、完全背包、分组背包如何统一到"容量-物品"框架？ A 分组背包每个物品可无限选 B 0-1 与完全背包枚举顺序相同 C 0-1 倒序、完全正序、分组先组后容量，统一在"容量-物品"框架下 ✓ 正确答案 D 背包问题无法统一建模
# 25. 区间 DP 的典型套路（合并石子/回文分割）中为什么先枚举区间长度？ A 先枚举区间长度再枚举端点，保证依赖的更短子区间已算好 ✓ 正确答案 B 应先枚举端点再枚举长度，否则出错 C 区间 DP 无需枚举分割点 D 区间 DP 复杂度恒为 O(n²)
# 26. 数位 DP 中'状态压缩'技巧中当 state 是集合（如已用数字集合）时用位掩码表示，以'不重复数字的整数个数'为例 A 状态压缩无法表示集合状态 B 已用数字集合用位掩码 mask 表示，转移时检查/置位，适配"不重复数字"统计 ✓ 正确答案 C 不重复数字统计不需要 mask D 位掩码只能表示 0-9 之外的状态
# 27. 数位 DP 求 [L,R] 内满足某数位性质的整数个数，为何通常转化为 f(R)-f(L-1)？L=0 时减一如何处理 A f(R)-f(L-1) 会算错区间 B 必须实现带下界约束的 DP，不能用差分 C L=0 时 f(L-1) 仍有效，无需特判 D [L,R] 计数用 f(R)-f(L-1)，L=0 时直接返回 f(R)（f(-1)=0） ✓ 正确答案
# 28. 数位 DP 的记忆化搜索框架（pos/state/limit/lead）如何设计？以统计 [1,N] 中不含连续 1 的整数个数为例说明各参数含义 A 不含连续 1 只需 pos 参数 B 记忆化必须缓存所有参数组合 C limit 与 lead 不影响记忆化 D 参数 pos/state/limit/lead 分别定位、携带性质、处理上界、处理前导零，只缓存 limit=false 的通用状态 ✓ 正确答案
# 29. 数位 DP 的"limit/isNum"记忆化参数如何设计，如何避免状态爆炸？ A 记忆化键包含所有 limit 状态，状态数爆炸 B limit 必须作为缓存键，否则出错 C 只缓存 limit=false 且 isNum=true 的通用状态，从缓存键剔除 limit，避免状态爆炸 ✓ 正确答案 D isNum 无需纳入状态
# 30. 树形 DP 的换根法（rerooting）何时适用，如何证明正确性？ A 换根法需要 O(n²) 时间 B 换根法只能用于单根，无法求所有根 C 换根法适用于"以每个节点为根"的答案，两次 DFS 从根向下换根，父答案已正确可归纳证明 ✓ 正确答案 D 换根法不需向下 DFS，只需一次遍历
