題目描述：

給定兩個(gè)字符串 text1 和 text2，返回這兩個(gè)字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。

一個(gè)字符串的 子序列 是指這樣一個(gè)新的字符串：它是由原字符串在不改變字符的相對(duì)順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
兩個(gè)字符串的 公共子序列 是這兩個(gè)字符串所共同擁有的子序列。

示例 1：

輸入：text1 = “abcde”, text2 = “ace”
輸出：3
解釋：最長公共子序列是 “ace” ，它的長度為 3 。
示例 2：

輸入：text1 = “abc”, text2 = “abc”
輸出：3
解釋：最長公共子序列是 “abc” ，它的長度為 3 。
示例 3：

輸入：text1 = “abc”, text2 = “def”
輸出：0
解釋：兩個(gè)字符串沒有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 僅由小寫英文字符組成。

解題思路一：動(dòng)規(guī)五部曲

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義
   dp[i][j]：長度為[0, i - 1]的字符串text1與長度為[0, j - 1]的字符串text2的最長公共子序列為dp[i][j]

有同學(xué)會(huì)問：為什么要定義長度為[0, i - 1]的字符串text1，定義為長度為[0, i]的字符串text1不香么？

這樣定義是為了后面代碼實(shí)現(xiàn)方便，如果非要定義為長度為[0, i]的字符串text1也可以，我在 動(dòng)態(tài)規(guī)劃：718. 最長重復(fù)子數(shù)組 (opens new window)中的「拓展」里 詳細(xì)講解了區(qū)別所在，其實(shí)就是簡化了dp數(shù)組第一行和第一列的初始化邏輯。

2. 確定遞推公式
   主要就是兩大情況： text1[i - 1] 與 text2[j - 1]相同，text1[i - 1] 與 text2[j - 1]不相同

如果text1[i - 1] 與 text2[j - 1]相同，那么找到了一個(gè)公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 與 text2[j - 1]不相同，那就看看text1[0, i - 2]與text2[0, j - 1]的最長公共子序列 和 text1[0, i - 1]與text2[0, j - 2]的最長公共子序列，取最大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

3. dp數(shù)組如何初始化
   先看看dp[i][0]應(yīng)該是多少呢？

test1[0, i-1]和空串的最長公共子序列自然是0，所以dp[i][0] = 0;

同理dp[0][j]也是0。

其他下標(biāo)都是隨著遞推公式逐步覆蓋，初始為多少都可以，那么就統(tǒng)一初始為0。

4. 確定遍歷順序
   從遞推公式，可以看出，有三個(gè)方向可以推出dp[i][j]，如圖：
   那么為了在遞推的過程中，這三個(gè)方向都是經(jīng)過計(jì)算的數(shù)值，所以要從前向后，從上到下來遍歷這個(gè)矩陣。

5. 舉例推導(dǎo)dp數(shù)組
   以輸入：text1 = “abcde”, text2 = “ace” 為例，dp狀態(tài)如圖：
   
   最后紅框dp[text1.size()][text2.size()]為最終結(jié)果

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:# 創(chuàng)建一個(gè)二維數(shù)組 dp，用于存儲(chǔ)最長公共子序列的長度dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]# 遍歷 text1 和 text2，填充 dp 數(shù)組for i in range(1, len(text1) + 1):for j in range(1, len(text2) + 1):if text1[i - 1] == text2[j - 1]:# 如果 text1[i-1] 和 text2[j-1] 相等，則當(dāng)前位置的最長公共子序列長度為左上角位置的值加一dp[i][j] = dp[i - 1][j - 1] + 1else:# 如果 text1[i-1] 和 text2[j-1] 不相等，則當(dāng)前位置的最長公共子序列長度為上方或左方的較大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])# 返回最長公共子序列的長度return dp[len(text1)][len(text2)]# 同意
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), 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] = max(dp[i-1][j], dp[i][j-1])else:dp[i][j] = dp[i-1][j-1] + 1return dp[-1][-1]

時(shí)間復(fù)雜度：O(nm)
空間復(fù)雜度：O(nm)

解題思路二：1維DP

class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:m, n = len(text1), len(text2)dp = [0] * (n + 1)  # 初始化一維DP數(shù)組for i in range(1, m + 1):prev = 0  # 保存上一個(gè)位置的最長公共子序列長度for j in range(1, n + 1):curr = dp[j]  # 保存當(dāng)前位置的最長公共子序列長度if text1[i - 1] == text2[j - 1]:# 如果當(dāng)前字符相等，則最長公共子序列長度加一dp[j] = prev + 1else:# 如果當(dāng)前字符不相等，則選擇保留前一個(gè)位置的最長公共子序列長度中的較大值dp[j] = max(dp[j], dp[j - 1])prev = curr  # 更新上一個(gè)位置的最長公共子序列長度return dp[n]  # 返回最后一個(gè)位置的最長公共子序列長度作為結(jié)果

時(shí)間復(fù)雜度：O(nm)
空間復(fù)雜度：O(n)

解題思路三：0

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)