uva 10405 - Longest Common Subsequence - solution

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;

#define mx 1001
char a[mx],b[mx];
int dp[mx][mx];
bool visited[mx][mx];

int lcs(int i,int j)
{
    if (a[i]=='\0' || b[j]=='\0') return 0;
    if (visited[i][j]) return dp[i][j];
    int ans=0;
    if (a[i]==b[j]) ans=1+lcs(i+1,j+1);
    else ans=max(lcs(i,j+1),lcs(i+1,j));
    visited[i][j]=true;
    dp[i][j]=ans;
    return dp[i][j];
}

int main()
{
    while (gets(a) && gets(b))
    {
        memset(visited,false,sizeof (visited));
        printf("%d\n",lcs(0,0));
    }
    return 0;
}