10405 - Longest Common Subsequence (UVA)

Simple & straight classical LCS algorithm :

Source code:

#include<bits/stdc++.h>
using namespace std;
int l1,l2,dp[1003][1003];
char s1[1003],s2[1003];
int len_LCS(int i,int j)
{
    if(i==l1 or j==l2)  return 0;
    if(dp[i][j]!=-1)     return dp[i][j];
    int ans=0;
    if(s1[i]==s2[j])
    {
        ans=1+len_LCS(i+1,j+1);
    }
    else
    {
        int val1=len_LCS(i+1,j);
        int val2=len_LCS(i,j+1);
        ans=max(val1,val2);
    }
    return dp[i][j]=ans;
}
int main()
{
    while(gets(s1) && gets(s2))
    {
        memset(dp,-1,sizeof(dp));
        l1=strlen(s1);
        l2=strlen(s2);
        printf("%d\n",len_LCS(0,0));
    }
    return 0;
}