动态规划算法实现最长公共子序列问题
从斐波那契数列看动态规划
斐波那契数列：
def fibnacci(n): if n == 1 or n==2: return 1 else: return fibnacci(n-1)+fibnacci(n-2) # print(fibnacci(100)) #--------------------------------------------------------- # 递归会出现子问题的重复计算 # f(6) = f(5)+f(4) # f(5) = f(4)+f(3) # f(4) = f(3)+f(2) # f(3) = f(2)+f(1) # 动态规划(DP)的思想=最优子结构==>递推式子(需要自己总结) + 重复子问题 def fibnacci_no_recurision(n): f = [0,1,1] if n>2: for i in range(n-2): num = f[-1]+f[-2] f.append(num) print(f) return f[n] # n==3 i==0 num=2 f=[0,1,1,2] # 子问题重复 # n==4 i==0 num=2 f=[0,1,1,2];i==1 num=3 f=[0,1,1,2,3] print(fibnacci_no_recurision(4))
钢条切割问题（递推式需要自己总结出来）
-----------------------------------------------------------------------------------------------------------------------------------------------------
钢条切割问题：自顶向下实现
时间复杂度O(2^n)---不采取
递归算法由于重复求解相同子问题，效率低
动态规划的思想：
每一次子问题只求解一次，保存求解结果
之后需要此问题时，只需要查找保存的结果
钢条切割问题：自底向上实现
最长公共子序列
一个序列的字序列式在该序列中删去若干元素后得到的序列
例：“ABCD”和“BDF”都是“ABCDEFG”的子序列
最长公共子序列(LCS)问题：给定两个序列X和Y，求X和Y长度最大的公共子序列
例：X="ABBCBDE" Y="DBBCDB" LCS(X,Y)="BBCD"
应用场景：字符串相似度比对
def lcs(x,y): m = len(x) n = len(y) c = [[0 for _ in range(n + 1)] for _ in range(m + 1)] # 1 左上方 2 上方 3 左方 b = [[0 for _ in range(n + 1)] for _ in range(m + 1)] for i in range(1,m + 1): for j in range(1,n + 1): # i,j位置上的字符匹配的时候，来自于左上方+1 if x[i-1] == y[j-1]: c[i][j] = c[i-1][j-1] + 1 b[i][j] = 1 # 来自于上方 elif c[i-1][j] > c[i][j-1]: c[i][j] = c[i-1][j] b[i][j] = 2 else: c[i][j] = c[i][j-1] b[i][j] = 3 print(c[m][n]) print(b) return c[m][n],b def lcs_trackback(x,y): c,b = lcs(x,y) i = len(x) j = len(y) res = [] while i > 0 and j > 0: # 来自左上方=>匹配 if b[i][j] == 1: res.append(x[i-1]) i -= 1 j -= 1 # 来自上方 elif b[i][j] == 2: i -= 1 # 来自于左方=>不匹配 else: j -= 1 return "".join(reversed(res)) print(lcs_trackback("ABCBDAB","BDCABA"))