Lintcode- Longest Common Subsequence(DP)

 Longest Common Subsequence(DP)

Given two strings, find the longest common subsequence (LCS).

Reference: https://www.youtube.com/watch?v=NnD96abizww
Complexity: O(n^2)

1. D[i][j] 定义为s1, s2的前i,j个字符串的最长common subsequence. 

2. D[i][j] 当char i == char j， D[i - 1][j - 1] + 1//diagonal

    当char i != char j,Max ( D[i ][j - 1], D[i - 1][j])top or left element

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String a, String b) {
        int m = a.length();
     int n = b.length();
     int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){
                if(i==0||j==0) dp[i][j]=0;//1st row&col is filled 0
                else if(a.charAt(i-1)==b.charAt(j-1)){//str index 1 ahead of dp 
                    dp[i][j]=1+dp[i-1][j-1];//if match, 1 + dp[i-1,j-1]diagonal
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);if not match, add max(top,left)
                }
            }
        }
     
     return dp[m][n];
    }
}