问题：
给定两个字符串，求他们的最长公共子序列的长度。
Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3. Example 2: Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3. Example 3: Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0. Constraints: 1 <= text1.length <= 1000 1 <= text2.length <= 1000 The input strings consist of lowercase English characters only.
解法：DP(动态规划)
1.确定【状态】：
- 字符串text1的第i个字符：text1[i]
- 字符串text2的第j个字符：text2[j]
2.确定【选择】：分两种情况
- text1[i] == text2[j]：
- 前一个字符状态(公共序列长度)+1: dp[i-1][j-1] + 1
- text1[i] != text2[j]：有以下3种情况，取最大值。
- 只有text1[i]是最终公共子序列的一个字符 -> =上一个包含text1[i]而不包含text2[j]的字符状态：dp[i][j-1]
- 只有text2[j]是最终公共子序列的一个字符 -> =上一个不包含text1[i]而包含text2[j]的字符状态：dp[i-1][j]
- 两个字符都不是最终公共子序列的一个字符 -> =上一个既不包含text1[i]又不包含text2[j]的字符状态：dp[i-1][j-1]
- ★由于dp[i-1][j-1]一定<=dp[i][j-1] or dp[i-1][j]，因此可以省略比较dp[i-1][j-1]
3. dp[i][j]的含义：
对比到text1的第 i 个字符，text2的第 j 个字符为止，两个字符串的最大公共子序列长度。
4. 状态转移：
dp[i][j]=
- (text1[i] == text2[j])：=前一个字符状态+1：dp[i-1][j-1] + 1
- (text1[i] != text2[j])：=max {
- 上一个包含text1[i]字符的状态：dp[i][j-1]
- 上一个包含text2[j]字符的状态：dp[i-1][j]
- 上一个text1[i]text2[j]都不包含的状态：dp[i-1][j-1]（★可省略） }
5. base case：
- dp[0][j]=0：text1为空串，则其与text2的公共子序列也一定为空串，长度为0。
- dp[i][0]=0：text2为空串，则其与text1的公共子序列也一定为空串，长度为0。
代码参考：
1 class Solution {
2 public:
3 //dp[i][j]:until text1[i],text2[j]. the max length of the LCS
4 //case_1: text1[i]==text2[j]:
5 // this character must be in LCS. we need add 1 to pre status:dp[i-1][j-1].
6 // =dp[i-1][j-1]+1
7 //case_2: text1[i]!=text2[j]
8 // text1[i] or text2[j] may in LCS. we choose the max of these possibilities.
9 // if text1[i] is in LCS,
10 // = dp[i][j-1]
11 // if text2[j] is in LCS,
12 // = dp[i-1][j]
13 // if none of them is in LCS,
14 // = dp[i-1][j-1]
15 // note: dp[i-1][j-1]<=dp[i-1][j](dp[i][j-1]) ,so we can ignore it
16 // =max(dp[i][j-1],dp[i-1][j])
17 //base case:
18 //dp[i][0]=0
19 //dp[0][j]=0
20 int longestCommonSubsequence(string text1, string text2) {
21 int m = text1.length(), n = text2.length();
22 vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
23 for(int i=1; i<=m; i++) {
24 for(int j=1; j<=n; j++) {
25 if(text1[i-1]==text2[j-1]) {
26 dp[i][j]=dp[i-1][j-1]+1;
27 } else {
28 dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
29 }
30 }
31 }
32 return dp[m][n];
33 }
34 };
♻️ 优化：
空间复杂度：2维->1维
去掉 i
压缩所有行到一行。
左上角dp[i-1][j-1]会被下面的dp[i][j-1]覆盖，因此引入变量pre，在更新dp[i][j-1]之前，保存dp[i-1][j-1]
代码参考：
1 class Solution {
2 public:
3 int longestCommonSubsequence(string text1, string text2) {
4 int m = text1.length(), n = text2.length();
5 vector<int> dp(n+1, 0);
6 for(int i=1; i<=m; i++) {
7 int pre = 0;
8 for(int j=1; j<=n; j++) {
9 int tmp = dp[j];
10 if(text1[i-1]==text2[j-1]) {
11 dp[j]=pre+1;
12 } else {
13 dp[j]=max(dp[j], dp[j-1]);
14 }
15 pre = tmp;
16 }
17 }
18 return dp[n];
19 }
20 };