从两个字符串中找到公共的最长子串： 例如：text1 = “abcad” test2 = “acd” 最长公共子串为acd，放回3
如果直接使用暴力求解，效率低，同时问题会比较复杂，要考虑很多情况，比如，“abdac” 和"acd"，此时的最长子串为ac或者ad，放回为2，这里的子串是有一定的顺序的。而不能直接用两个for循环，依次比较每个位置的字符就能解决的。这种求法需要把所有的情况包括进行，比较复杂。
第二种方法是递归法，只需要考虑一个最小问题即可。
考虑两种情况：
text1 = “…x” 和 text2=",x" 假设text1长度为n，text2长度为m 省略的地方表示其他的字符，我们从后往前看。 最后一个字符相同，所以剩下的相同的子串会出现在前面的字符串中，因此我们只需要考虑text1剩下的n-1长度部分和text2的m-1长度部分
第二种情况是 text1 = “…y” 和 text2=",x" 最后一个字符不等，那么text1的前n-1的字符串可能会和text2有相同的子串，text2的前m-1的字符串也可能会和text1有相同的子串，最后取它们的最大的情况。
因此我们可以写出递归的代码：
class Solution(object): def longestCommonSubsequence(self, text1, text2): """ :type text1: str :type text2: str :rtype: int """ # brute force too complicated # recurse time exceeded # dp method return self.lcs(text1, text2, len(text1), len(text2)) def lcs(self,text1, text2, l1, l2): if l1 == 0 or l2 == 0: result = 0 elif text1[l1-1] == text2[l2-1]: result = self.lcs(text1, text2, l1-1, l2-1) + 1 else: temp1 = self.lcs(text1,text2,l1-1,l2) temp2 = self.lcs(text1,text2,l1,l2-1) result = max(temp1, temp2) return result s = Solution() text1 = "abcde" text2 = "ace" s.longestCommonSubsequence(text1, text2) # output: 3在递归的基础上增加一个数组来保存每一次计算的值，那么就变成动态规划的memo方法：
class Solution(object): def longestCommonSubsequence(self, text1, text2): """ :type text1: str :type text2: str :rtype: int """ # brute force too complicated # recurse time exceeded # dp method l1 = len(text1) + 1 l2 = len(text2) + 1 arr = [[0 for i in range(l2)] for i in range(l1)] return self.lcs(text1, text2, len(text1), len(text2), arr) def lcs(self,text1, text2, l1, l2, arr): if arr[l1][l2] != 0: return arr[l1][l2] if l1 == 0 or l2 == 0: result = 0 elif text1[l1-1] == text2[l2-1]: result = self.lcs(text1, text2, l1-1, l2-1, arr) + 1 else: temp1 = self.lcs(text1,text2,l1-1,l2, arr) temp2 = self.lcs(text1,text2,l1,l2-1, arr) result = max(temp1, temp2) arr[l1][l2] = result return result s = Solution() text1 = "abcde" text2 = "ace" s.longestCommonSubsequence(text1, text2) # output: 3将上述的递归方法改成从下到上的模式，就是bottom-up 方法：
class Solution(object): def longestCommonSubsequence(self, text1, text2): """ :type text1: str :type text2: str :rtype: int """ # brute force too complicated # recurse time exceeded # dp method # bottom up n = len(text1) m = len(text2) arr = [[0]*(m+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,m+1): if text1[i-1] == text2[j-1]: arr[i][j] = 1 + arr[i-1][j-1] else: arr[i][j] = max(arr[i][j-1],arr[i-1][j]) return arr[-1][-1] s = Solution() text1 = "abcde" text2 = "ace" s.longestCommonSubsequence(text1, text2) # output:3其核心的迭代公式是没有变的，时间复杂度为O(mn)，其运算的效率要比前两种方法快一点，代码也更简洁一点。
