Dynamic Programming using Good old C++ ^_^


#1
int Solution::solve(string A, string B) 
{
    int n1 = A.length();
    int n2 = B.length();
    int arr[n1+1][n2+1];
    
    //making first row zero
    for(int i=0;i<=n2;i++)
        arr[0][i] = 0;
    
    //making first column zero
    for(int i=0;i<=n1;i++)
        arr[i][0] = 0;
        
    for(int i=1;i<=n1;i++)
    {
        for(int j=1;j<=n2;j++)
        {
            if(A[i-1] == B[j-1])//match, add diagonal + 1
            {
                arr[i][j] = arr[i-1][j-1] + 1;
            }
            else//maximum of top or left
            {
                arr[i][j] = max(arr[i-1][j],arr[i][j-1]);
            }
        }
    }
    
    return arr[n1][n2];
}