LC 97
Interleaving String
Medium · LC 1–100
候选解法路线
Primary
Free线性 DP / 一维状态递推
Invariant: 计算完 i 后，所有不超过 i 的状态都等于其定义下的真实最优值/计数；任何未来转移只读取这些已完成状态。
candidate confidence: 0.400 · metadata_only
Alternate 1
Free状态压缩 DP
Invariant: dp[mask] 是所有恰形成 mask 的合法序列中最优者；只从已正确的较小状态转移。
candidate confidence: 0.368 · metadata_only
Alternate 2
Free子序列 DP
Invariant: 每个已计算状态严格对应其末端/前缀定义，并已考虑所有合法的最后匹配、跳过或编辑动作。
candidate confidence: 0.350 · metadata_only
Alternate 3
Free网格 DP
Invariant: 处理 (r,c) 时，它依赖的所有邻格状态已符合定义；写入后 dp[r][c] 汇总了所有合法进入方式且无遗漏重复。
candidate confidence: 0.350 · metadata_only
如何使用本页
先读原题与 constraints，再逐一验证 Recognition signals、invariant 与 complexity；candidate score 不能证明正确性。