动态规划解法

使用动态规划（DP）来解决 LCS 问题，定义 dp[i][j] 表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的 LCS 长度。

状态转移方程

1. 如果 a[i] == b[j]：
   • 当前字符可以加入 LCS，所以 dp[i][j] = dp[i-1][j-1] + 1。
2. 如果 a[i] != b[j]：
   • 当前字符不能同时加入 LCS，所以取 dp[i-1][j]（不考虑 a[i]）和 dp[i][j-1]（不考虑 b[j]）的最大值：
     • dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

初始化

• dp[0][j] = 0（a 为空时，LCS 长度为 0）。
• dp[i][0] = 0（b 为空时，LCS 长度为 0）。

最终答案

• dp[n][m] 即为两个字符串的 LCS 长度。

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 1000 + 5;

char a[N],b[N];
int dp[N][N];

int main(){
	while(scanf("%s%s",a+1,b+1) == 2)
	{
		int n = strlen(a+1);
		int m = strlen(b+1);
		memset(dp,0,sizeof dp);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
				else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
			}
		}
		printf("%d\n",dp[n][m]);
	}
}