动态规划（下）：最长公共子序列、最长递增子序列、编辑距离

好，咱们接着聊动态规划。上一章我们把 DP 的套路捋了一遍，今天来啃三个硬骨头——最长公共子序列（LCS）、最长递增子序列（LIS）和编辑距离。这三个问题，说白了就是字符串和序列处理里的“三座大山”。我在做嵌入式协议解析时，没少跟它们打交道。

一、最长公共子序列（LCS）

先问个问题：给你两个字符串，怎么找出它们都包含的最长顺序子序列？注意，是子序列，不是子串。子序列可以不连续，但顺序不能乱。

举个例子，"abcde" 和 "ace" 的 LCS 是 "ace"，长度 3。这个在基因序列比对、文件 diff 里都用得上。我当年做嵌入式 OTA 差分升级时，就用 LCS 来算新旧固件的公共部分，减少传输量。

状态定义

定义 dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度。为什么用 i-1 和 j-1？为了方便处理空串，dp[0][j] 和 dp[i][0] 都是 0。

状态转移方程

if (text1[i-1] == text2[j-1])
    dp[i][j] = dp[i-1][j-1] + 1;
else
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

逻辑很直观：字符相等，长度加一；不等，取左边或上边的最大值。嗯，这里要注意，很多人会写成 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])，其实没必要，因为 dp[i-1][j-1] 一定小于等于另外两个。

代码实现

int longestCommonSubsequence(char* text1, char* text2) {
    int m = strlen(text1), n = strlen(text2);
    int dp[m+1][n+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
        }
    }
    return dp[m][n];
}

二、最长递增子序列（LIS）

LIS 的问题描述很简单：给定一个无序数组，找出最长的严格递增子序列长度。比如 [10,9,2,5,3,7,101,18] 的 LIS 是 [2,5,7,101]，长度 4。

这个问题的经典解法有两种：O(n²) 的 DP 和 O(n log n) 的贪心+二分。我个人更推荐后者，尤其是处理大数据时。

O(n²) 解法

定义 dp[i] 为以 nums[i] 结尾的 LIS 长度。对于每个 i，遍历 j < i，如果 nums[j] < nums[i]，就更新 dp[i] = max(dp[i], dp[j] + 1)。

int lengthOfLIS(int* nums, int numsSize) {
    int dp[numsSize], maxLen = 1;
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
        }
        if (dp[i] > maxLen) maxLen = dp[i];
    }
    return maxLen;
}

O(n log n) 解法——贪心+二分

这个思路很巧妙：维护一个数组 tails，tails[k] 表示长度为 k+1 的递增子序列的末尾元素最小值。遍历每个数，用二分查找找到它在 tails 中的位置，然后替换。

int lengthOfLIS(int* nums, int numsSize) {
    int tails[numsSize], len = 0;
    for (int i = 0; i < numsSize; i++) {
        int left = 0, right = len;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < nums[i])
                left = mid + 1;
            else
                right = mid;
        }
        tails[left] = nums[i];
        if (left == len) len++;
    }
    return len;
}

三、编辑距离（Levenshtein Distance）

编辑距离，就是将一个字符串变成另一个字符串所需的最少操作次数。操作有三种：插入、删除、替换。这个在拼写纠错、DNA 序列比对里太常见了。

我记得有一次做嵌入式语音识别后处理，用户说“打电话给张三”，识别成了“打电话给张山”，编辑距离一算，距离为 1，直接自动纠正了。

状态定义

dp[i][j] 表示 word1[0..i-1] 转换成 word2[0..j-1] 的最小编辑距离。

状态转移方程

if (word1[i-1] == word2[j-1])
    dp[i][j] = dp[i-1][j-1];
else
    dp[i][j] = min(
        dp[i-1][j] + 1,    // 删除 word1[i-1]
        dp[i][j-1] + 1,    // 插入 word2[j-1]
        dp[i-1][j-1] + 1   // 替换
    );

完整代码

int minDistance(char* word1, char* word2) {
    int m = strlen(word1), n = strlen(word2);
    int dp[m+1][n+1];
    
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i-1] == word2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else {
                int del = dp[i-1][j] + 1;
                int ins = dp[i][j-1] + 1;
                int rep = dp[i-1][j-1] + 1;
                dp[i][j] = del < ins ? (del < rep ? del : rep) : (ins < rep ? ins : rep);
            }
        }
    }
    return dp[m][n];
}

四、三种 DP 的对比与总结

问题	状态定义	时间复杂度	空间复杂度	典型应用
LCS	dp[i][j]：两串前缀的公共子序列长度	O(mn)	O(mn) 可优化为 O(n)	文件 diff、基因比对
LIS	dp[i]：以 nums[i] 结尾的 LIS 长度	O(n²) 或 O(n log n)	O(n)	任务调度、最长上升趋势
编辑距离	dp[i][j]：两串前缀的编辑距离	O(mn)	O(mn) 可优化为 O(n)	拼写纠错、语音识别后处理

你想想看，这三个问题其实都有一个共同点：它们都是二维 DP 的典型代表。LCS 和编辑距离是二维表格填表，LIS 虽然是一维数组，但优化后的二分思想也值得反复品味。

五、知识体系图

下面这张图把三个问题的核心逻辑串起来了，方便你对比记忆：

这三个问题，你只要把状态定义和转移方程吃透了，以后遇到类似的 DP 题，基本都能套上。说白了，动态规划就是“把大问题拆成小问题，用小问题的答案拼出大问题的答案”。

好了，这一章的内容就到这。代码多敲几遍，表格多画几次，你自然就找到感觉了。