Given two strings, find the longest comment subsequence (LCS). Your code should return the length of LCS. Example For "ABCD" and "EDCA", the LCS is "A" (or D or C), return 1 For "ABCD" and "EACB", the LCS is "AC", return 2
题目里说了：
Clarification
What‘s the definition of Longest Common Subsequence?
*(Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.) It is a classic computer science problem, the basis of file comparison programs such as diff, and has applications in bioinformatics.
1. D[i][j] 定义为s1, s2的前i,j个字符串的最长common subsequence.
2. D[i][j] 当char i == char j， 可以有三种选择，D[i - 1][j - 1] + 1，D[i ][j - 1], D[i - 1][j] ，取最大的
当char i != char j, D[i ][j - 1], D[i - 1][j] 里取一个大的（因为最后一个不相同，所以有可能s1的最后一个字符会出现在s2的前部分里，反之亦然。
1 public class Solution { 2 /** 3 * @param A, B: Two strings. 4 * @return: The length of longest common subsequence of A and B. 5 */ 6 public int longestCommonSubsequence(String A, String B) { 7 // write your code here 8 int[][] res = new int[A.length()+1][B.length()+1]; 9 for (int i=1; i<=A.length(); i++) { 10 for (int j=1; j<=B.length(); j++) { 11 res[i][j] = Math.max(A.charAt(i-1)==B.charAt(j-1)? res[i-1][j-1]+1 : res[i-1][j-1], 12 Math.max(res[i-1][j], res[i][j-1])); 13 } 14 } 15 return res[A.length()][B.length()]; 16 } 17 }
Lintcode: Longest Common Subsequence
原文：http://www.cnblogs.com/EdwardLiu/p/4322681.html