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[...