一、題目解析

對于給定了兩個字符串中，需要找到最長的公共子序列，也就是兩個字符串所共同擁有的子序列。

二、算法原理

1、狀態表示

?

dp[i][j]：表示s1的[0,i]和s2的[0,j]區間內所有子序列，最長子序列的長度

2、狀態轉移方程

根據最后一個位置的狀態，分情況討論

?

dp[i][j] s1[i]==s2[j]->dp[i-1][j-1]+1

? ? ? ? ? s1[i]!=s2[j]->max(dp[i][j-1],dp[i-1][j])

3、初始化

由于需要dp[i][j-1]和dp[i-1][j]，為了便于初始化計算最長子序列，可以多加一行一列，并初始化值為0，為了方便下標映射，可以對字符串前加一個空格處理，使其下標對其，便于操作

4、填表順序

?

為了避免所需值為計算，從上往下，從左往右開始填表

5、返回值

需要返回的是在s1和s2長度下的最長公共子串，所以return dp[m][n]?

依舊先畫圖思考，在自己實現，鏈接：1143. 最長公共子序列 - 力扣（LeetCode）

三、代碼示例

?

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));text1 = " "+text1;text2 = " "+text2;for(int i = 1;i<=m;i++){for(int j = 1;j<=n;j++){if(text1[i] == text2[j]){dp[i][j]= dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];}
};

?

?

看到最后，如果對您有所幫助，還請點贊、收藏和關注，點點關注不迷路，我們下期再見！?

?

?