【算法笔记】动态规划--前缀动态规划问题

【最长公共子序列问题】

问题定义:

输入:X = (x1,x2,...,xm) , Y = (y1,y2,...yn)

输出:公共子序列长度(拓展:如何打印公共子序列)

\1. 如何用子问题表示

dp[ i ][ j ]表示X的i前缀与Y的j前缀的最长公共子序列长度

则总问题==dp[ m ][ n ];

\2. 优化子结构和重叠子问题

\3. 递归表达式

if X[ i ] == Y[ j ] ,则dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1;

else, 则dp[ i ][ j ] = max{ dp[ i-1 ][ j ] , dp[ i ][ j-1 ] }

递归终点:dp[ i ][0]=dp[0][ j ]=0;(0<=i<m,0<=j<n)

\4. 设计数据结构:

与编号动态规划问题不同的是,递归是二维的形式,则设计成二维数组

\5. 伪代码

注意:对于这类二维动态规划,常常根据填表的方式(1)设计算法.(2)根据填表的顺序打印出序列

  • 确定填表方式
img
  • 数据结构: C[ i ][ j ]表示最大公共序列长度(即dp[ i ][ j ]), B[ i ][ j ]表示如何填表(便于回溯时打印序列)。

1)最大长度

For i = 0 To m C[ i ][ 0 ] = 0;

For j = 0 To n C[ 0 ][ j ] = 0;

//根据填表过程设计循环(从左到右,从上到下)

For i = 1 To m

For j = 1 To n

​ if xi = yj

​ C[ i ][ j ] = C[ i-1 ][ j-1 ] + 1 ; B[i,j] = “↖”;

​ else if C[ i-1][ j ] > C[ i ][ j-1 ]

​ C[ i ][ j ] = C[ i-1 ][ j ] ; B[i,j] = “ ↑ ”;

​ else

​ C[ i ][ j ] = C[ i ][ j - 1 ] ; B[i,j] = “ ← ”;

return C and B

2)如何打印数组

Print-LCS(B,X,i,j)

IF i=0 or j=0 THEN Return;

IF B[i,j]=“↖”

​ THEN Print-LCS(B,X,i-1,j-1);

​ Printxi;

ELSE If B[i,j]=“↑”

​ THEN Print-LCS(B,X,i-1,j);

ELSE

​ Print-LCS(B,X,i,j-1).

\6. 算法复杂度分析

O(mn)

【字符串的编辑距离】

问题定义:

串A ~> 串B 有三种操作(插入、删除、替换)

求最小的编辑操作代价

\1. 如何用子问题表示

在编辑的过程中,我们维护两个下标 i 和 j ,分别指向A和B中的位置

  • 插入:i不变,j++ 代价:1
  • 删除:i++,j不变 代价:1
  • 替换:i++,j++ 代价:0或1

dp[ i ][ j ]表示指针分别指向第 i 位和第 j 位时的编辑次数

则,当串A的指针指向m,串B的指针指向n时完成编辑

即总问题==dp[ m ][ n ]

\2. 优化子结构和重叠子问题

\3. 递归表达式

dp[ i ][ j ] = min{ dp[ i-1 ][ j-1 ] + d , dp[ i-1 ][ j ] + 1 , dp[ i ][ j-1 ] + 1 }

if ai==bj d=0, else d=1.

递归终点:dp[ i ][ 0 ] = i;dp[ 0 ][ j ] = j

\4. 伪代码

For i = 0 To m

dp[ i ][ 0 ] = i;//删除

For j = 0 To n

dp[ 0 ][ j ] = j;//插入

//根据填表过程设计循环(从左到右,从上到下)

For i = 0 To m

For j = 0 To n

​ dp[ i ][ j ] = min{ dp[ i-1 ][ j-1 ] + d , dp[ i-1 ][ j ] + 1 , dp[ i ][ j-1 ] + 1 }