Longest Common Subsequence

Problem:

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

Your code should return the length of LCS.

Have you met this question in a real interview? 

Yes

Clarification

What's the definition of Longest Common Subsequence?

• https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
• http://baike.baidu.com/view/2020307.htm

Example

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

Analysis:

4/6/2018 update:

if A[i - 1] != B[j - 1], why do we need to consider deleting A[i - 1]  and B[j - 1] separately? 

It is common sense that the max LCS will be the max of dp[i - 1][j] and dp[i][j-1]. What else choice do we have!
思路：
匹配DP画矩阵

state: dp[i][j], 第一个string 前i个和第二个string 前j个的LCS.
transition:  if(A[i-1]==B[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1])