企业官网建设流程全解析

• 文档
• 教程
• 示例工程

本文围绕《算法导论》（Introduction to Algorithms）第 15.4 节"最长公共子序列（Longest Common Subsequence, LCS）"的六道习题展开，系统讲解 LCS 长度的计算、路径重建、记忆化递归优化、空间压缩，以及最长单调递增子序列（LIS）的 O(n²) 与 O(n lg n) 两种解法。全文以仓库中的 15.4.md 为骨架，结合 lincrs.cpp 源码给出可运行实现，读者学完后既能完整推导 LCS/LIS 的递推关系，也能写出空间最优的工程级代码。

一、问题背景：从动态规划最优子结构谈起

LCS 问题要求给定两个序列 X =<x1, x2, ..., xm>与 Y =<y1, y2, ..., yn>，找出同时是二者子序列的最长序列。其核心递推式为：

• 若x[i] = y[j]，则c[i,j] = c[i-1,j-1] + 1；
• 否则c[i,j] = max(c[i-1,j], c[i,j-1])。

其中c[i,j]表示X[1..i]与Y[1..j]的 LCS 长度。15.4 节的习题从基础实例计算、路径回溯、记忆化、空间优化到复杂度升级层层递进，下面逐题展开。

二、Exercise 15.4-1：手算一组具体序列的 LCS

确定序列<1, 0, 0, 1, 0, 1, 0, 1>与<0, 1, 0, 1, 1, 0, 1, 1, 0>的一个 LCS。

15.4.md 给出的答案为：<1, 0, 0, 1, 1, 0>，或等价地<1, 0, 1, 0, 1, 0>。

验证思路：按递推式填一张 m×n 的表，从c[1,1]逐项计算到c[m,n]。题目给定的两个序列长度分别为 8 与 9，LCS 长度为 6。注意 LCS 不唯一——多个长度相同的公共子序列都是合法答案，这正说明"一个 LCS"而非"唯一 LCS"。读者可自行按递推式填表核对：两个候选答案都同时是两个序列的子序列，且长度均为 6，满足最优性。

三、Exercise 15.4-2：不使用 b 表，在 O(m+n) 内重建 LCS

标准教材用 b 表记录每个c[i,j]的取值方向（左上 / 上 / 左）。本习题要求只凭 c 表重建 LCS：

PRINT_LCS(c, x, y, i, j) if i = 0 || j = 0 return if x[i] = y[j] PRINT_LCS(c, x, y, i-1, j-1) print x[i] elif c[i-1, j] >= c[i, j-1] PRINT_LCS(c, x, y, i-1, j) else PRINT_LCS(c, x, y, i, j-1)

为什么成立：当x[i] = y[j]时，该字符必然属于某个 LCS，直接沿(i-1, j-1)回溯；当二者不等时，c[i,j]必然继承自c[i-1,j]与c[i,j-1]中的较大者（相等时任意选择，此处约定优先向上i-1），因此仅凭 c 表的数值即可判断移动方向，无需额外的 b 表。每步递归要么i减一、要么j减一，最多经过 m+n 次调用，所以总时间为 O(m+n)，匹配习题要求的复杂度。

四、Exercise 15.4-3：LCS 的记忆化（Memoized）版本，O(mn) 时间

自上而下的递归写法直接照搬递推式会有大量重叠子问题，记忆化通过"查表 - 未计算则递归求值并回填"避免重复：

LCS-LENGTH(X, Y) m ← length[X] n ← length[Y] for i ← 1 to m do for j ← 1 to n do c[i,j] ← -1 end for end for return LOOKUP-LENGTH(X, Y, m, n) LOOKUP-LENGTH(X, Y, i, j) if c[i,j] > -1 then return c[i,j] end if if i = 0 or j = 0 then c[i,j] ← 0 else if X[i] = Y[j] then c[i,j] ← LOOKUP-LENGTH(X, Y, i-1, j-1) + 1 else c[i,j] ← max(LOOKUP-LENGTH(X, Y, i, j-1), LOOKUP-LENGTH(X, Y, i-1, j)) end if end if return c[i,j]

实现要点：

• 先用 -1 初始化 c 表，作为"尚未计算"的哨兵值（LCS 长度非负，-1 不会与合法结果冲突）；
• 每个子问题(i, j)至多被计算一次，每次计算是常数时间，因此总复杂度为 O(mn)，与自底向上填表同阶；
• 边界条件i = 0 或 j = 0直接返回 0，对应空序列的 LCS 长度。

记忆化与自底向上（bottom-up）在最优子结构相同的前提下互为表里，前者天然保留递归语义、只计算真正需要的子问题，适合对表格局部求解的场景。

五、Exercise 15.4-4：把 c 表空间压缩到 2·min(m,n) 乃至 min(m,n)

计算c[i,j]只依赖三个邻居：c[i-1,j-1]、c[i,j-1]、c[i-1,j]。这意味着整张表不需要常驻内存，只需滚动保存最近两行：

因为求解一个项 c[i,j]，只会用到 c[i-1,j-1]、c[i,j-1]、c[i-1,j]。所以运行时刻，我们只需要保存上面一行的状态和当前行的状态即可。再令 X、Y 这两个字符串中短的那一个放到 index j，所以可以用 2 · min(m, n) 的空间运行算法。

原文档中文说明的关键工程细节：

1. 2 · min(m, n) 方案：保留"上一行 + 当前行"两个一维数组即可完成整轮填表。为保证行数取较小者，把 X、Y 中较短的那个序列映射到列方向（index j），于是行数为 min(m, n)，总占用 2 · min(m, n)。
2. min(m, n) 方案：更进一步，只保留一行。c[i,j-1]（当前行左侧）本来就在该行中；再用一个额外变量保存c[i-1,j-1]（上一行左上角）。每次更新c[i,j]时，先把旧值（即c[i-1,j]）暂存进这个额外变量，供下一列计算c[i-1,j-1]使用——这正是滚动数组（rolling array）在 LCS 上的经典落地。

Since we need only c[i-1,j-1], c[i,j-1], c[i-1,j] to compute c[i,j], we just need to save the previous row and the current row of the dp table. We will maintain the row parallel to the shorter one of the X and Y strings. So we can run the algorithm with 2 · min(m, n) space. In fact, we only need to save only one row. c[i,j-1] is already stored in this row. Then, we use an extra variable to maintain c[i-1,j-1]. Every time c[i,j] is updated, the value of c[i-1,j] is saved into the extra variable because it will be used next time.

需要强调的是：空间压缩只保留长度信息。若还要重建 LCS 序列本身，15.4-2 的 PRINT_LCS 依赖完整 c 表回溯；在滚动数组场景下可退化为"只求长度"或配合额外策略（如 Hirschberg 算法）折中。工程上需根据"要长度还是要序列"决定是否接受压缩。

六、Exercise 15.4-5：LIS 的 O(n²) 算法

设计 O(n²) 时间算法，求 n 个数的最长单调递增子序列。

原文档给出两种方法：

方法一：规约到 LCS

1. 将序列 X =<x1, x2, ..., xn>排序得到有序序列 X'；
2. 求 X 与 X' 的 LCS，即得 X 的最长单调递增子序列。

复杂度分析：排序 O(n lg n)，LCS-LENGTH 为 O(n²)，总时间 O(n²)。（注意：若元素不互异，需先做去重或改用严格递增的等价规约。）

方法二：直接 DP

LONGEST-INC-SEQUENCE(Arr, n) len [1..n] 为新建数组 for i ← 1 to n len[i] ← 1 // 以 i 结尾的最长递增序列长度 for i ← 2 to n do for j ← 1 to i-1 do if Arr[j] < Arr[i] len[i] ← max(len[i], len[j] + 1) end if end for end for return len[n]

len[i]表示"以Arr[i]为结尾的最长递增子序列长度"。对每个 i，扫描其左侧所有 j，凡Arr[j] < Arr[i]即可把len[j]的结果延长一位。双层循环使时间达到 O(n²)，空间 O(n)。严格递增的判定条件是Arr[j] < Arr[i]（若需非严格递增则改为<=）。

七、Exercise 15.4-6 ★：LIS 的 O(n lg n) 算法与仓库实现

给出 O(n lg n) 时间算法求最长单调递增子序列。提示：长度为 i 的候选子序列的末元素，不小于长度为 i-1 的候选子序列的末元素。通过输入序列链接候选子序列。

这是本节唯一标记 ★ 的习题，也是面试与工程实践中的高频考点。贪心 + 二分的核心思想是：

• 维护数组c，其中c[i]表示"所有长度为 i 的递增子序列中，最小的末尾元素"；
• 由提示可知，c天然是单调递增的，因此可以在 O(lg n) 内二分定位"第一个大于等于Arr[i]的位置 j"；
• 用Arr[i]覆盖c[j]（得到一个更优的、末尾更小的长度为 j 的子序列），若 j 超出当前已知长度则扩展最长长度。

仓库中的 lincrs.cpp 即该习题的实现，核心代码如下：

#include <iostream> using namespace std; int find(int *a, int len, int n) { int left(0), right(len), mid = (left + right) / 2; while (left <= right) { if (n > a[mid]) left = mid + 1; else if (n < a[mid]) right = mid - 1; else return mid; mid = (left + right) / 2; } return left; } int main() { int n, a[100], c[100], i, j, len; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; c[0] = -1; c[1] = a[0]; len = 1; for (i = 1; i <= n; i++) { j = find(c, len, a[i]); c[j] = a[i]; if (j > len) len = j; } cout << len << endl; return 0; }

代码要点解读：

• find对单调数组c[1..len]做二分查找，返回"第一个 ≥ n 的位置"（即 lower_bound 语义），找不到时返回left，恰好是应插入的新位置；
• 初始化c[0] = -1作为哨兵、c[1] = a[0]作为首元素，len记录当前已知 LIS 长度；
• 每处理一个元素做一次二分，共 n 次，总复杂度 O(n lg n)；
• 程序从标准输入读入 n 与 n 个数，输出 LIS 长度。可从命令行编译运行验证，例如g++ lincrs.cpp -o lincrs && ./lincrs后输入测试数据。

该实现只求长度；若需输出具体子序列，可额外用pre[]数组记录每个位置的前驱，在更新c[j]的同时维护链式链接，与习题提示"通过输入序列链接候选子序列"完全对应。

八、从习题到工程：复杂度与空间对照总结

九、延伸：动态规划解题模式小结

通过 15.4 节的完整练习，可以归纳出动态规划解题的通用四步：

1. 刻画最优子结构：LCS 的c[i,j]、LIS 的len[i]都能由更小的子问题递推得到；
2. 递归定义最优值：写出c[i,j]与len[i]的递推方程；
3. 自底向上或记忆化计算：按序填表，或带哨兵记忆化递归；
4. 构造最优解：如 15.4-2 的 PRINT_LCS，沿 c 表回溯输出序列。

结合仓库中 C15-Dynamic-Programming 目录的其他实现（如 rodcutting.cpp、Matrix-chain-multiplication.c、Assembly-line-sche.c），可以看到同一套"递推 + 填表 + 回溯"范式贯穿整章。读者可将 lincrs.cpp 作为模板，进一步练习输出 LIS 序列的变体，从而真正把 O(n lg n) 的贪心二分思想内化为可迁移的算法能力。

• 文档
• 教程
• 示例工程