Leetcode 1143. Longest Common Subsequence (python+cpp)

题目

解析：

前面碰到过很多道跟这种sequence相关的题目了，在这题里分析分析这种题目本质上应该怎么考虑。在前面碰到的题目里比如300 longest increasing subsequence，139 wordbreak,这些题目都是用动态规划来解非常经典的题目，但是如果你看过我前两道题的解析，会发现我在这些解法前面都加了一种recursion的方法，也可以理解为是brutal force，但这些解法毫无疑问都是超时的。
那么为什么要放这些解法呢，因为其实动态规划都是在brutal force解法上演变过来的。借着这道题来讲讲他是怎么演变的。
首先我们来看看brutal force应该怎么解这道题，brutal force其实是从两个string的末尾开始往前倒推recursion来解决的。现在我们定义一个recursion函数叫LSC(text1,text2).从末尾开始考虑，逻辑应该是这样：

if text1[curr_pos]==text2[curr_pos]:LCS(text1,text2) = 1 + LCS(text1[:-1],text2[:-1])
else:LCS(text1,text2) = max(LCS(text1[:-1],text2),LCS(text1,text2[:-1]))

总体的recursion逻辑就是这样。但是这样的时间复杂度会是O(2^L).但是看上面的逻辑判断，会有一种感觉就是怎么跟动态规划的状态转移方程这么像呢。其实这道题的动态规划解法就是基于这种recursion的思想。
我们定义一个二维dp数组，形状为(m+1,n+1)，m,n代表text1和text2的长度，状态转移方程为：

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

两种方法对比我们就可以发现，其实本质上：

dp[i-1][j-1]等价于LCS(text1[:-1],text2[:-1])
dp[i-1][j]等价于LCS(text1[:-1],text2)
dp[i][j-1]等价于LCS(text1,text2[:-1])

这样就很清晰了。两种方法的原理是一模一样的，只是一个是recursive的解决，一个是iterative的解决。如果想要更清晰的理解这个问题，推荐看下面这个视频https://www.youtube.com/watch?time_continue=1518&v=ASoaQq66foQ&feature=emb_logo。

recursive解法python代码如下：

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:def dfs(str1,str2):if not str1 or not str2:return 0if str1[-1]==str2[-1]:return 1+dfs(str1[:-1],str2[:-1])else:return max(dfs(str1[:-1],str2),dfs(str1,str2[:-1]))return dfs(text1,text2)

虽然recursion是TLE的，但是通过memorization来消除一些重复操作就可以通过提交了，代码如下：

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:def dfs(str1,str2):if not str1 or not str2:return 0if (str1,str2) in memo:return memo[(str1,str2)]if str1[-1]==str2[-1]:memo[(str1,str2)] = 1+dfs(str1[:-1],str2[:-1])else:memo[(str1,str2)] = max(dfs(str1[:-1],str2),dfs(str1,str2[:-1]))return memo[(str1,str2)]memo = {
    }return dfs(text1,text2)

动态规划解法python代码如下：

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m = len(text1)n = len(text2)dp = [[0]*(n+1) for _ in range(m+1)]for i in range(1,m+1):for j in range(1,n+1):if text1[i-1] == text2[j-1]:dp[i][j] = 1+dp[i-1][j-1]else:dp[i][j] = max(dp[i-1][j],dp[i][j-1])return dp[m][n]

动态规划解法C++代码如下：

class Solution {
    
public:int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));for (int i=1;i<=m;i++){
    for (int j=1;j<=n;j++){
    if (text1[i-1]==text2[j-1]){
    dp[i][j] = 1+dp[i-1][j-1];}else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}return dp[m][n];}
};