学步园

给定两个序列，求两个序列的最长公共子序列的长度（暂时先列出来长度好了……）
如此经典的DP，我竟然现在才弄明白，真心弱爆了，好吧，废话不说了，开始吧。
对于两个序列，dp[i][j]表示当第一个序列取前i个元素，第二个序列取前j个元素的时候，最长公共子序列的长度，那么对于此状态，有如下几种推导方式，假设第一个序列是X（x₁,x₂...x_i），第二个序列是Y（y₁,y₂...y_j），如果x_i=y_j，则dp[i][j]=dp[i-1][j-1]+1，否则，就等于dp[i-1][j]或者dp[i][j-1]。理由如下，假设X和Y的最长公共子序列为Z（z₁,z₂,...z_k），如果x_i=y_j，必然有x_i=y_j=z_k，如果x_i≠y_j，而且x_i≠z_k，则Z必然是X_i-1和Y的一个最长公共子序列，因为x_i存在与否根本不影响最终的结果，而z_k必然存在于X的前i-1个元素中，否则不成立，同理可运用于Y序列，所以可以得到推导关系。
刚刚把代码YY出来，不知道对不对，希望某一个大牛出来指正一下……

特别鸣谢：磊哥ZLGG

#include <cstdio>
#include <cstring>
#include <algorithm>
char x[1111], y[1111];
int dp[1111][1111];
int main(){
	scanf("%s", x);
	scanf("%s", y);
	int lx = strlen(x), ly = strlen(y);
	for (int i = 1; i <= lx; i++)
		for (int j = 1; j <= ly; j++)
			if (x[i] == y[j]) dp[i][j] = std::max(dp[i - 1][j - 1] + 1, std::max(dp[i - 1][j], dp[i][j - 1]));
			else dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
	printf("%d\n", dp[lx][ly]);
	return 0;
}