《算法设计与分析基础》（Python语言描述） 课件 第8章动态规划(2).pptx

8.1动态规划概述;8.5字符串动态规划;一个字符串的子序列是指从该字符串中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后得到的字符序列。

例如ace是abcde的子序列，但aec不是abcde的子序列。

给定两个字符串a和b，称字符串c是a和b的公共子序列，是指c同是a和b的子序列。该问题是求两个字符串a和b的最长公共子序列（LCS）。;设计二维动态规划数组dp，其中dp[i][j]为（a0，a1，…，ai-1）和（b0，b1，…，bj-1）的最长公共子序列长度，求dp[i][j]的两种情况。;dp[0][0]=0 初始条件

dp[i][0]=0 边界情况

dp[0][j]=0 边界情况

dp[i][j]=dp[i-1][j-1]+1 a[i-1]=b[j-1]

dp[i][j]=max{dp[i][j-1]，dp[i-1][j]} a[i-1]≠b[j-1];1 defLCSlength(a,b): #求dp

2 globaldp

3 m,n=len(a),len(b)

4 dp=[[0]*(n+1)foriinrange(m+1)]

5 dp[0][0]=0

6 foriinrange(m+1): #将dp[i][0]置为0

7 dp[i][0]=0

8 forjinrange(0,n+1): #将dp[0][j]置为0

9 dp[0][j]=0

10 foriinrange(1,m+1):

11 forjinrange(1,n+1): #循环处理a、b所有字符

12 ifa[i-1]==b[j-1]: #情况①

13 dp[i][j]=dp[i-1][j-1]+1

14 else: #情况②

15 dp[i][j]=max(dp[i][j-1],dp[i-1][j])

16 returndp[m][n];当求出dp后如何利用dp求一个最长公共子序列呢？分析状态转移方程最后两行的计算过程可以看出：

若dp[i][j]=dp[i-1][j-1]+1，有a[i-1]=b[j-1]，也就是说 a[i-1]/b[j-1]是LCS中的字符。

若dp[i][j]=dp[i][j-1]，有a[i-1]≠b[j-1]，也就是说 a[i-1]/b[j-1]不是LCS中的字符。

若dp[i][j]=dp[i-1][j]，有a[i-1]≠b[j-1]，同样 a[i-1]/b[j-1]不是LCS中的字符。;用一个字符串subs存放一个LCS，i=m，j=n开始向subs中添加k=dp[m][n]个字符，归纳为如下3种情况：

若dp[i][j]=dp[i-1][j]（即当前dp元素值等于上方相邻元素值），移到上一行即i减1，此时a[i]/b[j]不是LCS字符。

若dp[i][j]=dp[i][j-1]（即当前dp元素值等于左边相邻元素值），移到左一列即j减1，此时a[i]/b[j]不是LCS字符。

其他情况只能是dp[i][j]=dp[i-1][j-1]+1，移到左上方即i减1同时j减1，此时a[i]/b[j]是LCS的字符，将a[i]/b[j]添加到subs中。;例如，a=abcbdb，m=6，b=acbbabdbb，n=9。;1 defgetasubs(a,b): #由dp构造subs

2 subs= #存放一个LCS

3 m,n=len(a),len(b)

4 k=dp[m][n] #k为a和b的最长公共子序列长度

5 i,j=m,n

6 whilek0: #在subs中放入最长公共子序列(反向)

7 ifdp[i][j]==dp[i-1][j]:

8 i-=1

9 elifdp[i][j]==dp[i][j-1]:

10 j-=1

11 else:

12 subs+=a[i-1] #subs中添加a[i-1]

13 i,j,k=i-1,j-1,k-1

14 ans=list(subs)

15 ans.reverse()

16 return.join(ans) #返回逆置subs的字符串;设a和b是两个字符串。现在要用最少的字符操作次数（最优编辑距离），将字符串a编辑为字符串b。这里的字符编辑操作共有3种：删除一个字符，插入一个字符或者