2. it
  3. 二维动态规划最长公共子序列

二维动态规划最长公共子序列

mac2024-01-30  37

Written with StackEdit.

二维动态规划

引入Ⅰ

一道很简单的奥数题: 一个 m × n m\times n m×n的方格, 从左上角到右下角的路线有多少种? 很容易想到上边和左边的所有节点的种数只有1,而对于其他的点有: F ( x , y ) = F ( x − 1 , y ) + F ( x , y − 1 ) F(x,y)=F(x-1,y)+F(x,y-1) F(x,y)=F(x−1,y)+F(x,y−1) 所以从[0][0]推导至目标点即可. 而用计算机自动化求解,就用到了二维的DP知识. 当然还会有更复杂的情况,比如路径堵塞等.

引入Ⅱ

设有一个三角形的数塔，顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，可以向左走，也可以向右走. 问题:当三角形数塔给出之后，找出一条从第一层到达底层的路径，使路径的值最大。若这样的路径存在多条，任意给出一条即可.

将树旋转为下图: F(0,0)=13 状态转移方程为 F ( i , j ) = m a x { F ( i − 1 , j − 1 ) , F ( i , j − 1 ) } ( i f   e x i x t s ) F(i,j)=max\{F(i-1,j-1),F(i,j-1)\}(if\ exixts) F(i,j)=max{F(i−1,j−1),F(i,j−1)}(if exixts) 也就是相连的两个节点.

Basic

二维DP维护一个二维数组,其决定函数包含两个元,状态转移方程要考虑两个已经求值的节点.

应用:最长公共子序列

和最长不降/升子序列不同,最长公共子序列需要考虑两个序列,使用的是二维数组进行维护

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列:公共子序列中长度最长的子序列。

给定两个序列 X = { x 1 , x 2 , … , x m } X=\{x_1,x_2,…,x_m\} X={x1​,x2​,…,xm​}和 Y = { y 1 , y 2 , … , y n } Y=\{y_1,y_2,…, y_n\} Y={y1​,y2​,…,yn​}，找出X和Y的一个最长公共子序列。

穷举

穷举每一个X的子序列,验证是否是Y的子序列.

X有2m个子序列每个子序列需要o(n)的时间来验证它是否是Y的子序列. 从Yn的第一个字母开始扫描下去,如果不是则从第二个开始 运行时间: o(n2m)

分析

设 X i X_i Xi​为X前i个成员的序列. C ( i , j ) C(i,j) C(i,j)为序列Xi和Yj的最大公共子序列的长度.

最优子结构

设X和Y最长公共子序列为 Z k Z_k Zk​

若 X m = Y n = Z k X_m=Y_n=Z_k Xm​=Yn​=Zk​, C ( m − 1 , n − 1 ) = k − 1 C(m-1,n-1)=k-1 C(m−1,n−1)=k−1若 X m ≠ Y n   a n d   Z k ≠ X m X_m\not =Y_n\ and\ Z_k\not =X_m Xm​​=Yn​ and Zk​​=Xm​, C ( m − 1 , n ) = k C(m-1,n)=k C(m−1,n)=k Z k ≠ T Y n Z_k\not =TY_n Zk​​=TYn​亦同.

状态转移

C ( i , j ) = 0 , w h e n   i j = 0 C ( i − 1 , j − 1 ) + 1 , w h e n   X i = Y j M A X { C ( i − 1 , j ) , C ( i , j − 1 ) } , w h e n   X i ≠ Y j C(i,j)=\\ 0,when\ ij=0\\C(i-1,j-1)+1,when\ X_i =Y_j\\MAX\{C(i-1,j),C(i,j-1)\},when \ X_i \not=Y_j C(i,j)=0,when ij=0C(i−1,j−1)+1,when Xi​=Yj​MAX{C(i−1,j),C(i,j−1)},when Xi​​=Yj​

代码示例

''' @Description: 使用递归的最长公共子序列 @Date: 2019-10-30 23:35:31 @Author: I-Hsien @LastEditors: I-Hsien @LastEditTime: 2019-10-30 23:49:14 ''' def build(arr1,arr2,i:int,j:int): if (i*j==0): return 0 if (arr1[i-1]==arr2[j-1]): return build(arr1,arr2,i-1,j-1)+1 if (arr1[i-1]!=arr2[j-1]): return max(build(arr1,arr2,i-1,j),build(arr1,arr2,i,j-1)) if __name__=="__main__": array=input().split() brray=input().split() print(build(array,brray,len(array),len(brray)))

改进:剪裁了每次递归传入的序列,减少递归内存开销.

''' @Description: 改进版本;剪裁了每次递归传入的序列. @Date: 2019-10-30 23:52:10 @Author: I-Hsien @LastEditors: I-Hsien @LastEditTime: 2019-10-30 23:59:52 ''' def build(arr1,arr2): if arr1 ==[] or arr2 ==[]: return 0 if (arr1[-1]==arr2[-1]): return build(arr1[:-1],arr2[:-1])+1 if (arr1[-1]!=arr2[-1]): return max(build(arr1[:-1],arr2),build(arr1,arr2[:-1])) if __name__=="__main__": array=input().split() brray=input().split() print(build(array,brray))

放OJ上跑还是爆栈了…XD 下回试试非递归?

最新回复(0)