【晴问算法】提高篇—动态规划专题—最长公共子序列

题目描述

现有两个字符串s1​​​​与s2​，求s1​​​​与s2​​​​的最长公共子序列的长度（子序列可以不连续）。

输入描述

第一行为字符串s1​​，仅由小写字母组成，长度不超过100；

第一行为字符串s2​​​，仅由小写字母组成，长度不超过100。

输出描述

输出一个整数，表示最长公共子序列的长度。

样例1

输入

sadstory adminsorry

输出

6

解释

最长公共子序列为adsory，长度为6。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100;
string s;
string t;
int dp[MAXN][MAXN];//记录子问题的解，dp[i][j]表示字符串s的前i个字符和字符串t的前j个字符的最长公共子序列长度
int main(){
	cin >> s >> t;
	int ls = s.length();
	int lt = t.length();
	for(int i=1;i<=ls;i++)//填表方式，用i和j作为索引访问数组时候从1开始
		for(int j=1;j<=lt;j++){//两层循环遍历s和t的每个字符，比较是否相等
			if(s[i-1] == t[j-1]){//第i-1个和第j-1个相等
				dp[i][j] = dp[i-1][j-1] + 1;//表示当前位置位置的最长公共子序列长度比前一个位置多1
			}else if(s[i-1] != t[j-1]){//如果字符不相等
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);//表示当前位置的最长公共子序列长度与前一个位置保持一致
			}
		}
	}
	printf("%d",dp[ls][lt]);//即s1和s2的最长公共子序列长度
	
}