一、 最长公共子序列
1. 问题
通过比较公共子序列的长度来判断两个序列是否相似，如ABCBCDA和ACBCCAD的最长公共子序列为ABCCD。
现在有两个序列
和
，找出X和Y的最长公共子序列（LCS）。
2. 子问题拆分
这个问题就是求所有公共序列，然后找出最长的那个，而如何计算序列的长度，就是一个递归的过程了，公式如下：
这个问题是几个动态规划问题中最好理解的一个，是一个二维遍历标记的过程，最后再遍历一遍标记就能获得结果，不再赘述，直接看伪代码。
3. 伪代码
LCS-LENGTH(X, Y) m <- length[X] n <- length[Y] for i <- 1 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 x[i] = y[i] 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 b and c PRINT-LCS(b, X, i, j) n = 0 l = 0 for k <- j downto 1 if n[i, k] > n l = k while(i != 0 and l != 0) if b[i, l] = "\" print X[i] i = i - 1 l = l - 1 else if b[i, j] = "|" i = i - 1 else l = l - 1
4.代码
二、 最优二叉查找树
一篇包含很多文字的文章，遍历整篇文章，在一棵包含所有文字（包括文章内的和文章外的字）的二叉树中查找对应的字，计算出总的查找次数，最优二叉查找树就是为了获取总查找最少次数（也就是求查找次数的期望值最小）这类问题而设计的算法。
1. 问题
假设一个文章有s个文字，其中共有n个不同的文字
，且已经按拼音排序 
，每个文字
搜索的概率为
，由于有某些文字不在该篇文章中，所以还会有n+1个虚拟文字 ，对应的概率为
，
代表所有小于
的值，
表示所有大于
的值，所有的概率
： ，一次搜索的期望代价为
表：每个文字对应的概率
|
i |
0 |
1 |
2 |
3 |
4 |
5 |
|
pi |
0.15 |
0.10 |
0.05 |
0.10 |
0.20 |
|
|
qi |
0.05 |
0.10 |
0.05 |
0.05 |
0.05 |
0.10 |
2. 子问题拆分
使用子结构的最优解来构造原问题的最优解。
为
到
的概率总和，那么
到
的期望代价为
进一步计算出：
最终推导出递归公式：
3. 伪代码
OPTIONAL-BST(p, q, n) for i <- 1 to n + 1 e[i, i - 1] <- q[i - 1] w[i, i - 1] <- q[i - 1] for l <- 1 to n for i <- 1 to n - l + 1 j = i + l - 1 e[i, j] <- 0X7FFFFFFF w[i, j] <- w[i, j - 1] + p[j] + q[j] for r <- i to j t <- e[i, r - 1] + w[i, j] + e[r + 1, j] if t < e[i, j] e[i, j] <- t root[i, j] <- r return e and root PRINT-BST(root, n, i, j) if j = n and i = 1 print "root is " root[i, j] if i < j if i <= root[i,j] - 1 print "k" root[i, root[i,j]-1] "is left of " root[i,j] PRINT-BST(root, n, i, root[i,j]-1) if root[i,j] + 1<= j print "k" root[root[i,j]+1, j] "is right of " root[i,j] PRINT-BST(root, n, root[i,j]+1, j) else if i = j //叶子节点 print "d" root[i, j] - 1 "is left of" root[i, j] print "d" root[i, j] "is right of" root[i, j] else //k仅有一个左子节点为k时 print "d" j "is right of k" j
说明：PRINT-BST有点复杂，在此稍加讲解，当打印整个树时，i应该为1，而j应该为n，即树的实际节点数（不包括虚拟节点）。root[i,j]表示在 到 之间的根，其中的值代表k的下表，我们通过OPTIONAL-BST获得的root数组：
|
j=1 |
j=2 |
j=3 |
j=4 |
j=5 |
|
|
i=1 |
1 |
1 |
2 |
2 |
4 |
|
i=2 |
2 |
2 |
2 |
4 |
|
|
i=3 |
3 |
4 |
5 |
||
|
i=4 |
4 |
5 |
|||
|
i=5 |
5 |
第一次进入时，i=1，j=5，root[i,j]=2，说明在 到 之间k2为根，然后再找i到2-1之间的根作为根的左节点，同样，2+1到j的根作为根的右节点，然后递归计算，就能获取到树的结构了。
4. 代码
#include <iostream> using namespace std; #define MAX 65536 double p[6] = {0.00,0.15,0.10,0.05,0.10,0.20}; double q[6] = {0.05,0.10,0.05,0.05,0.05,0.10}; void optimal_bst(float e[][6],int root[][6],float w[][6],int n) { int i = 0,j = 0; for (i = 1; i <= n + 1; i++) { e[i][i - 1] = q[i - 1]; w[i][i - 1] = q[i - 1]; } int l = 0; for (l = 1; l <= n; l++) { for (i = 1; i <= n - l + 1; i++) { j = i + l - 1; e[i][j] = MAX; w[i][j] = w[i][j - 1] + p[j] + q[j]; for (int r = i; r <= j; r++) { double t = 0; t = e[i][r - 1] + e[r + 1][j] + w[i][j]; if (t < e[i][j]) { e[i][j]= t; root[i][j] = r; } } } } } void print_bst(int root[][6], int n, int i, int j) { int newI, newJ; if((i == 1)&&(j == n)) cout<<"K["<<root[i][j]<<"]"<<" is the root"<<endl; if (i < j) { newI = root[i][j] - 1; newJ = root[i][j] + 1; if(i <= newI) cout<<"k["<<root[i][newI]<<"]"<<" is the left child of k["<<root[i][j]<<"]"<<endl; print_bst(root,n, i,root[i][j] - 1); if(newJ <= j) cout<<"K["<<root[newJ][j]<<"]"<<" is the right child of K["<<root[i][j]<<"]"<<endl; print_bst(root,n, root[i][j] + 1,j); } if (i == j) { cout<<"d["<<i - 1<<"]"<<" is left child of k["<<i<<"]"<<endl; cout<<"d["<<i<<"]"<<" is right child of k["<<i<<"]"<<endl; } if(i > j) cout<<"d["<<j<<"]"<<" is right child of k["<<j<<"]"<<endl; } int main() { float e[7][6]; int root[6][6]; float w[6][6]; memset(e, 0, 7*6*sizeof(float)); memset(w, 0, 6*6*sizeof(float)); memset(root, 0, 6*6*sizeof(int)); optimal_bst(e,root,w,5); for(int i = 1; i <= 5; i++){ for(int j= 1; j <= 5; j++) cout<<root[i][j]<<" "; cout<<endl; } cout<<endl; for(int i = 1; i <= 6; i++){ for(int j= 0; j <= 5; j++) cout<<e[i][j]<<" "; cout<<endl; } cout<<endl; print_bst(root,5,1,5); return 0; }