POJ 1458 Common Subsequence (DP 动态规划)

#include <stdio.h>
#include <string.h>
#define MAX_LEN 1000
#define MAX(x, y) ( (x) > (y) ? (x) : (y) )

char str1[MAX_LEN];
char str2[MAX_LEN];
//lenOfLCS[i][j]表示字符串str1的i个前缀和字符串str2的j个前缀的LCS的长度
int lenOfLCS[MAX_LEN][MAX_LEN];//length of longest common subsequence

int main(){

	while (scanf("%s%s", &str1[1], &str2[1]) != EOF){
		int m = strlen(&str1[1]);
		int n = strlen(&str2[1]);
		int i, j;
		for (i = 0; i <= m; i++)
			for (j = 0; j <= n; j++)
				lenOfLCS[i][j] = 0;

		for (i = 1; i <= m; i++)
			for (j = 1; j <= n; j++)
				if (str1[i] == str2[j])
					lenOfLCS[i][j] = lenOfLCS[i - 1][j - 1] + 1;
				else 
					lenOfLCS[i][j] = MAX(lenOfLCS[i - 1][j], lenOfLCS[i][j - 1]);

		printf("%d\n", lenOfLCS[m][n]);
				
	}
	return 0;
}