突然发现自己有很长一段时间没有学习和更新算法相关的内容了。当然这并不完全是因为懒，主要还是临近毕业事务较多没能顾得上，做题的也感觉生分了许多。

什么是最长公共子序列（LCS, Longest Common Sequence）

关于 LCS 网络上有两种不同的含义，一个是“最长公共字符串（Longest Common String）”，一个是“最长公共子序列（Longest Commo Sequence）”。二者存在一定的差别，本文单独就后者进行相关的讨论。

最长公共子序列是动态规划中的一个经典的问题，即给定序列 A 和序列 B，然后求出两个序列中最大的公共子序列的长度，且该公共子序列中的元素可以不相邻。这类型的题目如果使用暴力解法一般都会直接顶满指数级的 $O(n^2)$ 复杂度，因此一般都会使用动态规划的写法来求解。

问题解法

LeetCode 上的对应题目见【1143. 最长公共子序列】。

首先介绍一下常规的暴力解法，直接通过递归来遍历所有可能的情况。代码如下：

def lcs(s1, s2):
    if s1 == "" or s2 == "":
        return 0
    elif s1[-1] == s2[-1]:
        return lcs(s1[:-1], s2[:-1])+1
    else:
        return max(lcs(s1, s2[:-1]), lcs(s1[:-1], s2))

这一写法显然存在着不足，即递归的部分会大量的重复，从而导致时间上的开销过大。因此，我们引入动态规划算法并建立矩阵进行相关数据的存储。假设两个字符串分别为 text1 和 text2，并定义dp[i][j] 为 text1 在 [0, i] 范围内的子串和 text2 在 [0, j] 范围内的子串的最长公共子序列。

• 状态转移：如果 text1[i-1]==text2[j-1]，那么说明我们找到了公共子串中的一个字符，则 dp[i][j] = dp[i-1][j-1] + 1；否则，如果 text1[i-1]!=text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])；
• 边界条件：如果两个字符串有一个为空，则 LCS 的长度就为 0，也就是 dp[0][.] = dp[.][0] = 0；

根据这样的思路，直接写出代码即可：

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        M, N = len(text1), len(text2)
        dp = [[0] * (N + 1) for _ in range(M + 1)]  # 初始化 DP 矩阵
        for i in range(1, M + 1):
            for j in range(1, N + 1):
                if text1[i - 1] == text2[j - 1]:  # 若匹配，则等于上一个状态 + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # 不匹配则取最大值
        return dp[M][N]

可以看出，这和背包问题也有一定的相似度，属于比较经典的动态规划问题。

其实还有一把梭的解法

当然，动态规划的本质就是“更有效率地递归”，因此大部分地动态规划题也是可以通过暴力解 + LRU Cache 的方式来降低时间复杂度的。这一道题中的 DP 矩阵当然也可以使用 LRU Cache 的方式来代替，即在暴力解法中对 lcs(s1,s2) 进行缓存即可，同样也可以得到一个十分不错的时间复杂度，甚至与动态规划相近。

在平常刷 LeetCode 的时候，我也发现大部分通过动态规划简化时间复杂度的问题里都会有大神通过 LRU Cache 来达到相同的效果。这其实属于一种一把梭的解法了，神乎其技且十分简单暴力，就是 LRU Cache 使用的地方经常需要考究（我曾经就找错过函数，结果没有任何优化效果）。

当然，这样做的代价也是有的，因为 LRU Cache 的本质上是在维护一个由输入参数作为键，函数返回值作为值的字典，因此比 DP 的矩阵要大上不少，空间复杂度相应也要高一些。