动态规划进阶：LCS、LIS与矩阵连乘

动态规划这东西，说实话，入门容易进阶难。很多朋友学完背包问题就觉得DP不过如此，结果一碰到字符串匹配、序列分析就懵了。今天咱们就来啃这三块硬骨头——最长公共子序列、最长递增子序列、矩阵连乘。我当年在做一个基因序列比对工具时，就是靠LCS算法撑起来的，那会儿踩的坑，现在想想还挺有意思。

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

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

比如"ABCBDAB"和"BDCABA"，它们的LCS是"BCBA"或"BDAB"，长度是4。怎么算？暴力枚举肯定不行，2的n次方级别的复杂度，字符串稍微长点就炸了。

状态定义与转移方程

我个人习惯用二维数组dp[i][j]表示：字符串A的前i个字符和字符串B的前j个字符的LCS长度。那么状态转移怎么推？

• 如果A[i] == B[j]，那这个字符肯定在LCS里，dp[i][j] = dp[i-1][j-1] + 1
• 如果不等，那就取max(dp[i-1][j], dp[i][j-1])，说白了就是跳过其中一个字符

嗯，这里要注意：边界条件dp[0][j]和dp[i][0]都是0，因为空串跟谁都没公共子序列。

int lcs(char *a, char *b) {
    int m = strlen(a), n = strlen(b);
    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 (a[i-1] == b[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];
}

回溯构造LCS

光知道长度不够，有时候你得把具体的子序列拿出来。怎么做？从dp[m][n]往回走：

• 如果a[i-1]==b[j-1]，这个字符就是LCS的一部分，然后往左上角走
• 如果不相等，看dp[i-1][j]和dp[i][j-1]谁大，往大的方向走
• 如果相等，随便选一个方向（但可能得到不同的LCS）

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

LIS这个问题，你想想看，给一个数组，找出最长的严格递增的子序列。比如[10,9,2,5,3,7,101,18]，LIS是[2,5,7,101]或[2,3,7,101]，长度4。

最直观的做法是O(n²)的DP，但说实话，在工程中我更常用O(n log n)的贪心+二分法。为什么？因为数据量一大，平方级就扛不住了。

O(n²)的DP解法

定义dp[i]为以第i个元素结尾的LIS长度。转移方程：

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;
}

最后取所有dp[i]的最大值。简单吧？但n=10000时，这个循环就要跑5000万次，有点慢。

O(n log n)的贪心+二分

这个思路很有意思。我维护一个数组tails，tails[k]表示长度为k+1的递增子序列中，最小的末尾元素。你想想看，末尾元素越小，后面越容易接上新的数，对吧？

int lengthOfLIS(int* nums, int numsSize) {
    int tails[numsSize];
    int len = 0;
    
    for (int i = 0; i < numsSize; i++) {
        // 二分查找第一个大于等于nums[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;
}

我在做股票交易系统的时候，就用这个算法分析价格序列的上升趋势。嗯，效果还不错，比单纯看均线灵敏多了。

三、矩阵连乘问题

这个问题，说白了就是：给你一堆矩阵，怎么加括号让乘法次数最少？注意，矩阵乘法满足结合律，不满足交换律，所以括号位置很关键。

比如三个矩阵A(10×100)、B(100×5)、C(5×50)：

• (AB)C：10×100×5 + 10×5×50 = 5000 + 2500 = 7500次乘法
• A(BC)：100×5×50 + 10×100×50 = 25000 + 50000 = 75000次乘法

你看，差了整整10倍！

状态定义

定义dp[i][j]为从第i个矩阵到第j个矩阵的最小乘法次数。p数组存储维度：矩阵i的维度是p[i-1]×p[i]。

转移方程：

dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])
// 其中 i ≤ k < j

什么意思？就是在k处断开，左边的最小代价加上右边的最小代价，再加上合并左右结果的代价。

int matrixChain(int p[], int n) {
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    
    // len是子问题的矩阵个数，从2开始
    for (int len = 2; len < n; len++) {
        for (int i = 1; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + 
                           p[i-1] * p[k] * p[j];
                if (cost < dp[i][j])
                    dp[i][j] = cost;
            }
        }
    }
    return dp[1][n-1];
}

四、知识体系总览

这三个问题虽然看起来不一样，但核心套路是相通的。我画了个图，帮你理清思路：

五、避坑指南与实战心得

做了这么多年嵌入式开发，我总结了几条关于DP的实战经验：

• 先画表格再写代码：遇到二维DP，先在纸上画个表格，手动填几个值，规律就出来了。我每次带新人都是这么教的。
• 注意下标偏移：LCS里dp[i][j]对应a[i-1]和b[j-1]，这个偏移搞错了，整个程序就废了。
• 空间优化要谨慎：滚动数组虽然省内存，但如果你需要回溯构造具体解，那就不能省，得保留完整dp表。
• 测试用例要覆盖边界：空串、单元素、全部相等、全部不等——这些情况都得测一遍。

好了，这三个问题就聊到这儿。你想想看，它们本质上都是在做同一件事——把大问题拆成小问题，用小问题的答案拼出大问题的答案。只不过LCS和LIS是序列上的DP，矩阵连乘是区间上的DP。套路学会了，以后遇到新问题，先想想能不能用DP，怎么定义状态，怎么转移——思路就打开了。

---

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