C++ 16 Lines O(n) space O(n^2) time DP


#1
> int Solution::solve(string A, string B) {
>     int mx = 0,  An = A.size(),  Bn = B.size(),  dp[An+1] = {0};
>     for(int j = Bn-1;j>=0;j--) //B
>     {
>         for(int i = 0;i<An;i++) //A
>         {
>             if(A[i]==B[j]) dp[i] = dp[i+1] + 1;
>         }
>         for(int i = An-1;i>=0;i--)
>         {
>             dp[i] = max(mx,dp[i]);
>             mx = max(mx,dp[i]);
>         }
>     }
>     return dp[0];
> }