牛客对应题目链接：最长公共子序列(一)_牛客题霸_牛客网 (nowcoder.com)
力扣对应题目链接：1143. 最长公共子序列 - 力扣（LeetCode）
一、分析题目
【动态规划 - 两个数组 / 字符串之间的 dp 问题】
1、状态表示
dp[i][j] 表示字符串 s1 中 [0, i] 区间与字符串 s2 中 [0, j] 区间中所有的子序列中，最长公共子序列长度。
2、状态转移方程
根据最后⼀个位置的字符情况，划分问题：
- s1[i] == s2[j]：dp[i][j] = dp[i - 1][j - 1] + 1
- s1[i] != s2[j]：dp[i][j] = max(dp[i - 1][j], do[i][j - 1])
3、初始化
dp[0][j] = dp[i][0] = 0
4、遍历顺序
从左往右
5、返回值
dp[n][m]
二、代码
//牛客AC代码 #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; string s1, s2; cin >> s1 >> s2; vector<vector<int>> dp(n+1, vector<int>(m+1)); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j], dp[i][j-1]); } } cout << dp[n][m] << endl; return 0; } //力扣AC代码 class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n=text1.size(), m=text2.size(); vector<vector<int>> dp(n+1, vector<int>(m+1)); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { 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[n][m]; } };
