原題鏈接： https://leetcode-cn.com/problems/longest-common-subsequence/

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長公共子序列的長度。
一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字符串的「公共子序列」是這兩個字符串所共同擁有的子序列。
若這兩個字符串沒有公共子序列，則返回 0。

image.png

解題思路

1. 當子序列text1的第i位與子序列text2的第j位相等時，其公共子序列的長度L1就等于子序列text1[0:i]和子序列text2[0:j]的最長公共子序列長度L2+1，即L1=L2+1；
2. 當子序列text1的第i位與子序列text2的第j位不等時，需要考慮兩種情況，即去掉第i位后的text1[0:i]與text2比較，或者text1與去掉第j位的text2[0:j]比較，取兩者的最大值即為text1[i]與text2[j]不等時的結果；
3. 用dp[i][j]二維數(shù)組來表示text1[0:i+1]與text2[0:j+1]的最長公共子序列長度，當text1[i]==text2[j]，dp[i][j]=dp[i-1][j-1]+1；當text1[i]!=text2[j]，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

Python3代碼

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1 = len(text1)
        n2 = len(text2)
        dp = [[0 for _ in range(n2+1)] for _ in range(n1+1)]
        for i in range(1, n1+1):
            for j in range(1, n2+1):
                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])
        return dp[-1][-1]