题目
给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。
给出"ABCD" 和 "EDCA"，这个LCS是 "A" (或 D或C)，返回1
给出 "ABCD" 和 "EACB"，这个LCS是"AC"返回 2
最长公共子序列的定义：
- 最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
- https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
解题
求的都是最长，应该动态规划求解.画图下面的图，1 的位置就是相同的元素。从（0,1）开始是第一个相同的元素A，后面的设为（i,j）要想是后续连续的公共子序列则，i>0 j>1 也就是说，后面点的横纵坐标一定要大于前面点的横纵坐标。
| E | A | C | B | |
| A | 1 | |||
| B | 1 | |||
| C | 1 | |||
| D |
这样可以定义一个很大的数组，如何根据数组中1出现的位置找到最长的子序列，设这个数组是Arr
Arr[i][j] =1 表示元素相同 ，如何找出下一个点的横坐标大于i 纵坐标大于j的，并且一直找下去。。。下面不知道怎么办了。。。
说得很好
设两个字符串是A、B ，其长度是lenA、lenB 定义数组Arr[lenA+1][lenB+1] ,Arr[i][j] 表示A[0--i] ,B[0--j] 两个字符串的最长公共子序列长度,对下面的一个位置 i+ 1 、j+ 1
1.若A[i+1] == B[j+1], 则Arr[i+1][j+1] = Arr[i][j] + 1
2.若A[i+1]!=B[j+1],Arr[i+1][j+1] 应该是根据其前面一个元素的值确定的，这里是个矩阵其前面的元素是Arr[i][j],Arr[i+1][j],Arr[i][j+1]
Arr[i][j]表示A[0--i] ,B[0--j] 两个字符串的最长公共子序列长度
Arr[i+1][j]表示A[0--i+1] ,B[0--j] 两个字符串的最长公共子序列长度
Arr[i][j+1]表示A[0--i] ,B[0--j+1] 两个字符串的最长公共子序列长度
A[i+1]!=B[j+1], 可能A[i+1]==B[j] A[i]==B[j+1] 这里是交叉相等的情况所以Arr[i+1][j+1] =max（Arr[i+1][j],Arr[i][j+1]）
同时要注意：数组Arr长度是lenA+1 lenB+1 第一行第一列的元素都是0 这样在求解的时候比较方便
Java
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) { // write your code here int lenA = A.length(); int lenB = B.length(); if(A== null || B == null||lenA == 0|| lenB ==0) return 0; int d[][] = new int[lenA + 1][lenB + 1]; for(int i=1;i<= lenA;i++){ for(int j=1;j<=lenB;j++){ // if(i==0) // d[i][j] = 0; // if(j==0) // d[i][j] = 0; char a = A.charAt(i-1); char b = B.charAt(j-1); if(a ==b ){ d[i][j] = d[i-1][j-1] + 1; }else{ d[i][j] = Math.max(d[i-1][j],d[i][j-1]); } } } return d[lenA][lenB]; }} Python
class Solution: """ @param A, B: Two strings. @return: The length of longest common subsequence of A and B. """ def longestCommonSubsequence(self, A, B): # write your code here if A == None or B==None or len(A) ==0 or len(B) == 0: return 0 lenA = len(A) lenB = len(B) d = [[0 for i in range(lenB+1)] for j in range(lenA+1)] for i in range(1,lenA+1): for j in range(1,lenB+1): if A[i-1] == B[j-1]: d[i][j] = d[i-1][j-1] + 1 else: d[i][j] = max(d[i-1][j],d[i][j-1]) return d[lenA][lenB]
递归求解超时
public int longestCommonSubsequence(String A, String B) { // write your code here int lenA = A.length(); int lenB = B.length(); if(A== null || B == null||lenA == 0|| lenB ==0) return 0; char a = A.charAt(0); char b = B.charAt(0); if( a == b){ String subA = A.substring(1); String subB = B.substring(1); return 1 + longestCommonSubsequence(subA,subB); }else{ String subA = A.substring(1); String subB = B.substring(1); int lcs1 = longestCommonSubsequence(A,subB); int lcs2 = longestCommonSubsequence(subA,B); return Math.max(lcs1,lcs2); } }