动态规划进阶：典型问题（LCS、LIS、编辑距离）

动态规划学到这个阶段，咱们得碰几个硬骨头了。

最长公共子序列、最长递增子序列、编辑距离——这三个问题，可以说是DP入门的「三座大山」。翻过它们，你的DP功力会上一个台阶。我当年面试大厂时，这三道题几乎轮着被考，一个都没落下。

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

先问个问题：给你两个字符串，怎么找出它们「都包含」的最长子序列？

注意，子序列不要求连续，但顺序必须一致。比如 "abcde" 和 "ace"，LCS 就是 "ace"，长度3。

状态定义

我习惯用 dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的LCS长度。

为什么是 i-1 而不是 i？因为这样方便处理空串，不用单独初始化边界。

状态转移

说白了就两种情况：

  • 如果 text1[i-1] == text2[j-1]，那这个字符肯定在LCS里，长度加1：dp[i][j] = dp[i-1][j-1] + 1
  • 如果不相等，那就取「去掉一个字符」后的最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

核心思想：两个字符串的匹配问题，通常用二维DP。行和列分别对应两个字符串的索引。

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] = fmax(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

小技巧：如果你只需要长度，可以优化成一维数组。但初学阶段，我建议先写二维，逻辑更清晰。

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

这个题我印象太深了。有一次做日志分析系统，需要从时间戳序列里找出最长的连续增长趋势，其实就是LIS的变种。

O(n²) 解法——最直观

定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。

转移方程：dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]。

int lengthOfLIS(int* nums, int numsSize) {
    int dp[numsSize];
    int 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[i] = fmax(dp[i], dp[j] + 1);
            }
        }
        maxLen = fmax(maxLen, dp[i]);
    }
    return maxLen;
}

O(n log n) 解法——进阶优化

你想想看，如果只求长度，能不能更快？

可以维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的「最小末尾元素」。

为什么这样做？因为末尾越小，越容易在后面接上更长的序列。嗯，这里要注意，这个数组不一定是真正的LIS，但它能帮我们算出长度。

int lengthOfLIS_optimized(int* nums, int numsSize) {
    int tails[numsSize];
    int 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;
}

避坑指南：我曾经在二分查找的边界条件上栽过跟头。记住，这里找的是「第一个大于等于 nums[i]」的位置，用左闭右开区间最稳。

三、编辑距离

编辑距离，也叫Levenshtein距离。它衡量的是把一个字符串变成另一个字符串，最少需要多少次操作。操作有三种：插入、删除、替换。

这个算法在拼写检查、DNA序列比对里用得很多。我做过一个简单的代码纠错工具，核心就是它。

状态定义

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

转移方程

  • 如果 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（不用操作）
  • 否则，取三种操作的最小值：
    • 插入：dp[i][j-1] + 1
    • 删除：dp[i-1][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 insert = dp[i][j-1] + 1;
                int delete = dp[i-1][j] + 1;
                int replace = dp[i-1][j-1] + 1;
                dp[i][j] = fmin(insert, fmin(delete, replace));
            }
        }
    }
    return dp[m][n];
}

记忆技巧：编辑距离的三种操作，对应到DP表里就是「左、上、左上」三个方向。你画个表格，走一遍就懂了。

知识体系总览

这三个问题虽然长得不一样，但骨子里是同一套思路：

  • LCS：二维DP，字符相等就斜着走，不等就取左/上最大值
  • LIS：一维DP，或者用二分优化到O(n log n)
  • 编辑距离：二维DP，三种操作对应三个方向取最小

它们共同的特点是：子问题之间有重叠，而且状态转移只依赖前几个状态。这就是DP能派上用场的地方。

动态规划进阶：三大典型问题 最长公共子序列 最长递增子序列 编辑距离 二维DP 字符相等 → 斜角+1 不等 → 左/上取最大 一维DP / 二分优化 dp[i] = max(dp[j]+1) tails数组 + 二分查找 二维DP 插入/删除/替换 左/上/左上取最小 共同核心：子问题重叠 + 状态转移

写在最后

这三个问题，我建议你亲手在纸上画一遍DP表。光看代码是不够的，你得理解每个格子是怎么来的。

特别是编辑距离，画一遍表之后，你会发现它和LCS其实有千丝万缕的联系——只不过LCS只考虑匹配，编辑距离还要考虑代价。

嗯，动态规划就是这样，看着复杂，拆开了也就是「状态 + 转移」四个字。多练几道，手感自然就来了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →