ブルーブリッジカップ最長共通サブシーケンス

2つの文字列が与えられ、S 1 S 2.....SnとT 1 T 2…Tn.この2つの文字列の中で最も長い共通サブシーケンスの長さを求めます.文字列S 1 S 2…Snのサブシーケンスとは、Si 1 Si 2を表すことができる.Simのシーケンス
 

/* 
*        ，                   
*        ，           1
*       ，      a    1  ，     b        1   
* 
*/ 
#include<stdio.h>
#include<string.h>
int N,M;
int dp[100][100];
char a[100],b[100];
int max(int n,int m){
return n>m?n:m;
}
void f(){
for(int i=0;i<N;i++)
for(int j=0;j<M;j++){
if(a[i]==b[j])    dp[i+1][j+1]=dp[i][j]+1;
else
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]); 
}
printf("%d",dp[N][M]);
}
int main(){
memset(dp,0,sizeof(dp));
scanf("%d%d",&N,&M);
getchar();
for(int i=0;i<N;i++)
scanf("%c",&a[i]);
getchar();
for(int j=0;j<N;j++){
scanf("%c",&b[j]);
}
f();
return 0;
}

 

/***************************************************/

#include<stdio.h>
#include<string.h>
int N,M;
int dp[100][100];
char a[100],b[100];
int max(int n,int m){
return n>m?n:m;
}
int rec(int i,int j){
if(dp[i][j]>=0) return dp[i][j];
int res=0;
if(i==N || j==M)
return 0;    
else if(a[i]==b[j]) res=rec(i+1,j+1)+1;  //       res+1
else
res=max(rec(i+1,j),rec(i,j+1));        //      ，                   
return dp[i][j]=res;
}
int main(){
memset(dp,-1,sizeof(dp));
scanf("%d%d",&N,&M);
getchar();
scanf("%s",a);
getchar();
scanf("%s",b);
printf("%d
",rec(0,0));
return 0;
}