抛出问题：
假定字符串 s1 = 'BDCABA', s2 = 'ABCBDAB',求s1和s2的最大公共子序列。
问题分析：
我们想要求出s1和s2的最大公共子序列，我们可以用c(i,j)表示s1（i）和s2（j）最大公共子序列的长度，
假定c(i,j) = m,
如果：s1[ i ]和s2[ j ]相等，那么推出c(i,j) = c(i-1,j-1) + 1，
如果：s1[ i ] 和 s2[ j ]不相等,那么得到c(i,j) = max(c(i,j-1),c(i-1,j))
总结为公式就是：
画成表格更清楚，也就是如下图，表格的数即为当前的最大公共子序列的值，箭头即为该结果是怎么得来的
例如第5行，第5列，因为第5列的c和第5行c相等，所以就等于，第4行，第4列的值+1等到2
得到了这个值列表，就可以通过回溯的方法，从最后一个值，倒着按照箭头的方向，依次记录每个相等的值（也就是方向是左上的值），得到的结果就是我们要求的最终结果
代码实现：
# -*- coding:utf-8 -*- # 日期：2018/6/9 15:44 # Author:小鼠标 # 求最长公共子序列 from numpy import * s1 = 'BDCABA' s2 = 'ABCBDAB' def val_list(s1,s2): # 两个字符串的长度 len_s1 = len(s1) + 1 len_s2 = len(s2) + 1 # 方向列表 direction_list = [] # 生成len_s2+1行len_s1+1列的全0列表 res = zeros((len_s2,len_s1)) direction = zeros((len_s2,len_s1)) # print(res_list) for i in range(0, len_s2-1): for j in range(0, len_s1-1): #判断是否相等 if s1[j] == s2[i]: res[i + 1, j + 1] = res[i, j] + 1 # 1左上 2 上 3左 direction[i + 1, j + 1] = 1 else: if res[i + 1, j] > res[i, j + 1]: res[i + 1, j + 1] = res[i + 1, j] direction[i + 1, j + 1] = 3 else: res[i + 1, j + 1] = res[i, j + 1] direction[i + 1, j + 1] = 2 return res,direction res ,direction= val_list(s1,s2) #方向列表 1左上 2 上 3左 # [[0. 0. 0. 0. 0. 0. 0.] # [0. 2. 2. 2. 1. 3. 1.] # [0. 1. 3. 3. 2. 1. 3.] # [0. 2. 2. 1. 3. 2. 2.] # [0. 1. 2. 2. 2. 1. 3.] # [0. 2. 1. 2. 2. 2. 2.] # [0. 2. 2. 2. 1. 2. 1.] # [0. 1. 2. 2. 2. 1. 2.]] #最大子序列的值列表 # [[0. 0. 0. 0. 0. 0. 0.] # [0. 0. 0. 0. 1. 1. 1.] # [0. 1. 1. 1. 1. 2. 2.] # [0. 1. 1. 2. 2. 2. 2.] # [0. 1. 1. 2. 2. 3. 3.] # [0. 1. 2. 2. 2. 3. 3.] # [0. 1. 2. 2. 3. 3. 4.] # [0. 1. 2. 2. 3. 4. 4.]] #回溯 递归求出结果 global s_res s_res = '' def Lcs_fun(s,res_list,i,j): if res_list[i,j] == 3: Lcs_fun(s,res_list,i,j-1) elif res_list[i,j] == 2: Lcs_fun(s,res_list,i-1,j) elif res_list[i,j] == 1: Lcs_fun(s,res_list,i-1,j-1) global s_res s_res += s[i-1] else: return Lcs_fun(s2,direction,len(s2),len(s1)) print(s_res)
这块很容易就看晕了，仔细看，应该能看懂