動态規劃算法實作最長公共子序列問題
從斐波那契數列看動态規劃
斐波那契數列:
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"))
lcs