UVA- 10192 : Vacation

//Problem link >>http://uva.onlinejudge.org/external/101/10192.html

...DP  problem  ...  LCS ...

#include <bits/stdc++.h>
using namespace std ;

 string s1 , s2 ;
 int x , y  , dp[103][103] ;

 int lcs(int i , int j)
 {
     if (i==x|| j==y) return 0 ;
     int  &bus=dp[i][j] ;

     if (bus !=-1) return bus ;

     if (s1[i]==s2[j])  return  bus=1+lcs(i+1 , j+1) ;

     return bus= max(lcs(i , j+1) , lcs(i+1 , j) ) ;

 }

int main ()
{
    int cas=0 ;
    while (getline(cin,s1) && s1!="#")
    {
        getline(cin,s2) ;
        x=s1.size() ;
        y=s2.size() ;

        memset(dp,-1,sizeof (dp)) ;

        cout<<"Case #"<<++cas<<": ";
       cout<<"you can visit at most "<<lcs(0,0)<<" cities."<<endl ;

     }
    return 0 ;
}

sample  input::

abcd
acdb
abcd
dacb
#

sample output:

Case #1: you can visit at most 3 cities.
Case #2: you can visit at most 2 cities.