最長共通サブシーケンス(LCS)

#include<cstdio>
#include<string.h>
#define max(a, b) a > b ? a : b
int dp[1010][1010];
char str1[1010], str2[1010];

int main()
{
	int n, len1, len2, i, j, len;
	scanf("%d", &n);
	while(n--)
	{
		scanf("%s%s", str1, str2);
		len1 = strlen(str1);
		len2 = strlen(str2);
		len = max(len1, len2);
		for(i = 0; i <  len; ++i)
		{
			dp[0][i] = 0;
			dp[i][0] = 0;
		}
		for(i = 1; i <= len1; ++i)
		{
			for(j = 1; j <= len2; ++j)
			{
				if(str1[i - 1] == str2[j - 1]) // 
					dp[i][j] = dp[i - 1][j - 1] + 1;
				else
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		printf("%d
", dp[len1][len2]);
	}
	return 0;
}

#include<iostream>
#include<string>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[1010][1010];
string str1, str2;

int main()
{
	int n, i, j, len;
	scanf("%d", &n);
	while(n--)
	{
		cin>>str1>>str2;
		str1 = "0" + str1;  // ， ,
		str2 = "0" + str2;
		for(i = 1; i < str1.length(); ++i)
		{
			for(j = 1; j < str2.length(); ++j)
			{
				if(str1[i] == str2[j])
					dp[i][j] = dp[i - 1][j - 1] + 1;
				else
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		printf("%d
", dp[str1.length() - 1][str2.length() - 1]);
	}
	return 0;
}

 
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int main()
{       
	char s1[1000],s2[1000];                             //         
	int r[1000],s[1000],L1,L2,i,j,k,t;   //DP ， ，L1 L2    
	scanf("%d",&t);
	while(t--)        
	{         
		scanf("%s%s",s1,s2);
		L1=strlen(s1);L2=strlen(s2);       
		for(i=0;i<=L2;++i)r[i]=0;         
		for(i=0;i<=L1;++i)s[i]=0;          
		for(i=0;i<L1;++i)          
		{               
			for(j=0;j<L2;++j)     
			{                 
				if(s1[i]==s2[j])    //           
					s[j+1]=r[j]+1;         
				else                   
					s[j+1]=r[j+1]>s[j]?r[j+1]:s[j];         // ，        
			}
			for(k=1;k<=L2;++k)       
				r[k]=s[k];                              //      
		}           
		printf("%d
",r[L2]);         
		//    
	}       
	return 0;
}