题目：
给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB 则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA思路
很简单的一道题 dp[i][j]就是指从a序列的i到b序列的j可以构成的最长公共子序列长度 你要想求dp[i][j] 如果a[i-1] == b[j-1] 那么这就是一种情况，说明dp[i][j]有可能是题解的一部分 如果不等，那么就得求dp[i-1,j]和dp[i,j-1]的最优解 具体遍历就直接右下遍历即可题解
#include<iostream> #include<algorithm> #include<cstring> using namespace std; char a[100],b[100]; int ans; int dp[100][100]; //i代表a的位置 j代表b的位置 int main(){ cin >>a; cin >>b; int len1 = strlen(a); int len2 = strlen(b); for(int i = 1;i<=len1;i++){ for(int j = 1;j<=len2;j++){ if(a[i-1] == b[j-1]){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = max(dp[i-1][j],dp[j][j-1]); } } } cout <<dp[len1][len2]<<endl; return 0; }