題目

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長公共子序列。

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

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字符串的「公共子序列」是這兩個字符串所共同擁有的子序列。

若這兩個字符串沒有公共子序列，則返回 0。

示例 1:

輸入：text1 = "abcde", text2 = "ace"

輸出：3

解釋：最長公共子序列是 "ace"，它的長度為 3。

示例 2:

輸入：text1 = "abc", text2 = "abc"

輸出：3

解釋：最長公共子序列是 "abc"，它的長度為 3。

示例 3:

輸入：text1 = "abc", text2 = "def"

輸出：0

解釋：兩個字符串沒有公共子序列，返回 0。

提示:

1 <= text1.length <= 1000

1 <= text2.length <= 1000

輸入的字符串只含有小寫英文字符。

解析（類似背包問題）

dp table

對于兩個子序列 S1 和 S2，找出它們最長的公共子序列。
定義一個二維數(shù)組 dp 用來存儲最長公共子序列的長度，其中 dp[i][j] 表示 S1 的前 i 個字符與 S2 的前 j 個字符最長公共子序列的長度?？紤] S1i 與 S2j 值是否相等，分為兩種情況：

1. 當 S1i==S2j 時，那么就能在 S1 的前 i-1 個字符與 S2 的前 j-1 個字符最長公共子序列的基礎(chǔ)上再加上 S1i 這個值，最長公共子序列長度加 1，即 dp[i][j] = dp[i-1][j-1] + 1。
2. 當 S1i != S2j 時，此時最長公共子序列為 S1 的前 i-1 個字符和 S2 的前 j 個字符最長公共子序列，或者 S1 的前 i 個字符和 S2 的前 j-1 個字符最長公共子序列，取它們的最大者，即 dp[i][j] = max{ dp[i-1][j], dp[i][j-1] }。

綜上，最長公共子序列的狀態(tài)轉(zhuǎn)移方程為：

image.png

對于長度為 N 的序列 S1 和長度為 M 的序列 S2，dp[N][M] 就是序列 S1 和序列 S2 的最長公共子序列長度。

 public int LongestCommonSubsequence(string text1, string text2)
    {
        if (text1.Length == 0 || text2.Length == 0) return 0;
        int[,] dp = new int[text1.Length + 1, text2.Length + 1];//初始化dp，dp的長度比字符串長度大一
        for (int i = 1; i <= text1.Length; i++)
        {
            for (int j = 1; j <= text2.Length; j++)
            {
                if (text1[i - 1] == text2[j - 1]) //此處是取字符串的上一位
                    dp[i, j] = dp[i - 1, j - 1] + 1; 
                else
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
            }
        }
        return dp[text1.Length, text2.Length];
    }