【算法笔记】动态规划--前缀动态规划问题
【最长公共子序列问题】
问题定义：
输入：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）根据填表的顺序打印出序列
- 确定填表方式
- 数据结构: 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 }