信息学奥赛一本通T1265- 最长公共子序列-题解（C语言代码）

解题思路:

假设两个字符串分别为s1, s2

dp[i, j]表示s1以s1[i - 1]结尾和s2以s2[i - 1]结尾结尾时的最长上升子序列的长度。

注意事项:

dp[len1][0] = dp[0][len2] = 0;

参考代码:

#include <stdio.h>
#include <string.h>
#define max(a, b) a > b ? a : b
char s1[1005], s2[1005];
int dp[1005][1005];

int main() {
	scanf("%s%s", s1, s2);
	int len1 = strlen(s1), len2 = strlen(s2);
	for (int i = 1; i <= len1; ++i) {
		for (int j = 1; j <= len2; ++j) {
			if (s1[i - 1] == s2[j - 1]) 
				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[len1][len2]);
	return 0;
}