最长公共子序列：
二维网格状态设计、栈溢出陷阱与回溯路径

从一维到二维：两个字符串的前缀网格

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列（LCS）的长度。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

与单数组递增子序列（LIS）不同，此处涉及两个互不相同的序列推进。如果尝试穷举子序列，时间复杂度将达到指数级 $O(2^M \times 2^N)$，不可承受。解题的本质在于观察两个前缀子串的末尾字符关系：

二维表格步进，观察对角线与正交转移。

推演双重循环逐步填满二维网格的过程。当字符匹配时，观察高亮的左上角对角线跨越；当字符不同时，观察正交方向的极值继承。推演完成后，深紫色高亮展示反向回溯重构出的公共子序列路径。

三个关键细节：内存栈溢出、下标偏移与回溯重构

1. 01

   大二维数组为何必须加 static？

   LeetCode 1143 题目给定的字符串长度上限为 1000。在 C 语言中，若在函数内部声明 int dp[1005][1005];，该数组会占用约 $1000 \times 1000 \times 4 \approx 4\text{ MB}$ 的栈空间。而在许多系统或编译器默认环境（例如 Windows MSVC 默认栈仅 1MB，部分评测环境 2~8MB）中，此操作会直接导致栈溢出崩溃（Stack Overflow）。将数组声明为 static int dp[MAXN][MAXN]; 或放在全局数据段，能彻底消除栈溢出隐患。

2. 02

   dp[i][j] 与 text[i - 1] 的“偏移 1”约定

   由于存在“空字符串”的基础边界，网格的第 0 行与第 0 列专门代表长度为 0 的前缀（此时 LCS 为 0）。因此，外层循环中的 i = 1..length1 表示考察“前 i 个字符”，而字符串在 C 语言中是 0-indexed 的，对应在数组中的访问下标恰好是 text1[i - 1]。切忌混淆 i 与 i - 1，否则会发生数组越界或少比对末尾字符。

3. 03

   不仅求长度，如何重构具体字符串？

   求出 dp[m][n] 仅得到了长度。若要还原真正的 LCS 字符串，可以从右下角 (m, n) 出发倒序回溯：若 text1[i - 1] == text2[j - 1]，则该字符属于 LCS，将其存入结果并移向 (i - 1, j - 1)；否则比较 dp[i - 1][j] 与 dp[i][j - 1]，沿着值更大的一侧后退。最终将收集到的字符逆序输出即可。

真实 C 语言实现节选

选自 CSP 练习记录中已通过评测的源码。使用静态二维表，逻辑直观，评测表现优异。

#include <stdio.h>
#include <string.h>

#define MAXN 1005

int longestCommonSubsequence(char *text1, char *text2) {
    // 关键细节 1：使用 static 避免 4MB 二维数组在函数调用栈中溢出
    static int dp[MAXN][MAXN];
    int length1 = strlen(text1);
    int length2 = strlen(text2);

    for (int i = 1; i <= length1; i++) {
        for (int j = 1; j <= length2; j++) {
            // 关键细节 2：前 i/j 个字符对应下标 i-1 与 j-1
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                if (dp[i - 1][j] > dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
    }
    return dp[length1][length2];
}

复杂度与滚动数组空间压缩