A93770题解

题目已经明确说明，这道题是让我们求最长公共子序列
什么是最长公共子序列？
最长公共子序列就是两个或多个字符串公共的子序列，并且是最长的
如：
abc
bcd
这两个字符串就有三个子序列
"b","c","bc"
但是我们要找最长的那个，所以是“bc”。所以答案为2（长度是2）
那怎么求呢
由于这是一道动态规划题，所以有3个步骤
1.定义状态
我们设dp[i][j]是指字符串 s 的前 i 项和 t 的前 j 项的最长公共子序列长度
2.转移方程
我们先看看dp[i][j]可以由哪里转移过来
第一条：如果s[i]和t[j]相等
那么dp[i][j]就可以从dp[i-1][j-1]转移过来，只要长度加1就可以了
第二条：如果它们的结尾不同
让我们来想一想，它们的结尾都不同了画黄色圈圈的两段字符串可能相同吗？

所以s[i]和t[j]中总有一个是没用的
因此我们就得到了转移方程
3.最终答案
根据状态的意思，我们就能知道，最终答案肯定是dp[s.size()][t.size()]

代码：

#include<iostream>
using namespace std;
const int N=2005;
int dp[N][N];
int main(){
	string s,t;cin>>s>>t;
	int len1=s.size();
	int len2=t.size();
	for(int i=1;i<=len1;i++){
		for(int j=1;j<=len2;j++){
            if(i+j<=1)continue;
			if(s[i-1]==t[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[len1][len2];
}