算法设计 — Wu Chenfeng

先建一个二维数组，不会自动得到动态规划。算法设计先定义状态、选择和重复子问题，再比较递归、分治、贪心与缓存。复杂度解释规模增长，实际布局和常数决定工程成本。

状态与求解策略

渐进复杂度

大O记号描述输入规模增大时的增长上界，忽略常数和低阶项。

常见：

$O(1)$ ：数组索引、平均哈希查找；
$O(\log N)$ ：平衡树查询、二分查找；
$O(N)$ ：扫描列表；
$O(N\log N)$ ：比较排序；
$O(N^2)$ ：所有对象两两比较。

还要区分最坏、平均与摊还。动态数组 push_back 偶尔扩容为 $O(N)$ ，但按倍数增长时摊还通常是 $O(1)$ 。

复杂度不是实际时间。连续扫描一百万整数可能比随机访问十万个节点更快，因为缓存、分支、分配和并行度不同。

递归与枚举

递归把问题写成规模更小的同类问题，必须有明确终止条件，并保证每次调用都向终止条件靠近。树遍历、文件层级和分治算法很适合递归表达。调用栈会保存局部状态，深度不受控时可能栈溢出，此时改用显式栈更安全。

枚举适合候选空间不大、正确性比复杂优化更重要的场景。写枚举前先列出状态、选择和剪枝条件，避免重复状态。回溯在一次选择后递归搜索，失败时撤销选择；若子问题会重复出现，可进一步使用记忆化或动态规划。

穷举并不等于粗糙。很多离线资产工具的数据量有限，清楚的 $O(N^2)$ 实现比难以验证的复杂结构更合适。先估算真实上界，再决定是否需要优化。

排序与分治

排序不仅为了显示，它还能让后续去重、区间扫描和确定性输出更简单。在只通过元素比较确定顺序的模型中，任意输入的最坏情况需要 $\Omega(N\log N)$ 次比较。归并排序时间稳定、适合顺序访问，需要额外空间；快速排序平均快且原地性好，但枢轴不佳时会退化；堆排序保证 $O(N\log N)$ ，局部性通常不如前两者。

稳定排序会保留相等元素原有顺序。资产构建若先按次要键排序，再按主要键做稳定排序，结果容易理解。并行构建和网络模拟需要稳定输出时，还应补一个唯一 ID 作为最终同分决胜规则。

分治把问题拆成相互独立的子问题，递归求解后合并。归并排序、BVH 构建和最近点问题都用这个思路。分析时既要看拆分后的规模，也要看合并成本；子问题大量重叠时，它更接近动态规划问题。

动态规划

动态规划适用于最优子结构且子问题重复的问题。先定义状态含义，再写转移、初始值和计算顺序。不要从二维数组开始猜公式。

最长公共子序列可令 $dp[i][j]$ 表示两个前缀的 LCS 长度。字符相同时从 $dp[i-1][j-1]+1$ 转移，否则取上方和左方最大值。它可用于文本或序列差异分析，但不是连续子串。只求长度时可滚动数组省内存，恢复实际序列则需要保留路径或重新回溯。

最长公共子序列的状态只保存两个前缀已经匹配的最大长度。对“AB”和“ACB”，比较最后字符B相同后，问题退到“A”和“AC”，长度再加1；字符不同则必须舍弃其中一侧的末字符，取两个子问题的较大值。按前缀长度递增填表，保证每个依赖先于消费者。

当只保存滚动两行时，空间从 $O(NM)$ 降到 $O(M)$ ，但恢复匹配位置需要额外路径或重算。这是输出需求改变存储需求的例子：只问长度与要完整编辑路径，是两个不同的验收目标。

记忆化是自顶向下递归并缓存结果，适合只访问少量状态；表格递推是自底向上填表，访问顺序和内存更可控。状态维度过多会带来内存爆炸，应检查是否能压缩状态或换一种建模。

最大子数组可令当前状态表示“必须以当前位置结尾的最大和”，转移只需比较从当前元素重新开始，或接在上一段之后。Kadane 算法因此能用 $O(N)$ 时间和 $O(1)$ 额外空间完成。

矩阵链乘法不改变矩阵顺序，而是选择括号位置减少标量乘法次数。状态 $dp[i][j]$ 表示第 $i$ 到 $j$ 个矩阵相乘的最小成本，枚举最后一次切分点 $k$ 。它展示了区间动态规划的基本结构：区间长度递增，答案由两个更短区间合并。

前缀递推

最长公共子序列的CPU伪代码定义dp[i,j]为两个前缀的最长长度，空前缀初始化为零。

text

if a[i-1] == b[j-1]: dp[i,j] = dp[i-1,j-1]+1
else: dp[i,j] = max(dp[i-1,j],dp[i,j-1])

贪心算法

贪心每一步选择当前看来最优的方案，不回退。它成立需要可证明的贪心选择性质和最优子结构，不能因为结果“看起来不错”就声称最优。区间调度按结束时间选择是经典例子，Dijkstra 在非负边上也包含贪心地确定最短节点。

贪心也先找能否交换的理由。区间调度按最早结束选取后，剩余可用时间不少于任意更晚结束的首个选择，所以可以递归处理余下区间。若每个区间带不同收益，同样规则可能错过高价值长区间，此时要重新建带收益的状态。给算法加字段会改变证明前提。

工程中常用近似贪心解决装箱、调度和 LOD 预算。此时要明确它是启发式，并用最坏场景与基线比较。一个简单贪心若结果稳定、速度足够且容易解释，往往比难维护的精确优化更实用。

字符串匹配与 KMP

朴素字符串匹配在每个起点重新比较，最坏为 $O(NM)$ 。KMP 为模式串预计算前缀函数，也叫失配函数，失配时利用已经匹配的前后缀长度跳转，不让文本指针回退，整体为 $O(N+M)$ 。

固定prefix[i]为模式前缀pattern[0:i+1]的最长真前后缀长度。模式ABABAC对应[0,0,1,2,3,0]。文本已经匹配ABABA，下一字符却为B，期待的C失配；已匹配长度5退到prefix[4]=3，因为末尾ABA可以作为下一轮开头。当前文本字符仍是B，它与模式第3位B匹配，长度恢复到4。文本字符没有回退，也没有丢弃已知的重叠结构。若把前缀长度误当下一比较字符的前一索引，重复前缀处会跳错，普通不重复字符串却可能掩盖这个错误。

实现 KMP 最容易出错的是前缀表定义不统一：有的保存长度，有的保存下一个索引。写代码时先固定 prefix[i] 的含义，并用重复前缀、全相同字符和空模式测试。资产路径规则、日志扫描和简单文本工具可以用它；常规业务代码优先使用标准库中经过验证的搜索实现。

验证方法

小输入用穷举对照，空、重复和退化输入验证边界。性能测规模曲线并保留工作负载；贪心最优性需要证明，启发式则明确近似目标。

实现与证据

正文LCS为数学伪代码，配有手工追踪例与带收益反例；尚未运行算法实现。复杂度按明确状态与操作推导，工程耗时待实际数据测量。

参考资料

MIT6.006课程资料：动态规划、最短路与复杂度讲义入口。