关于最长公共子序列（LCS）
最长公共子序列和最长公共子串是有区别的，之前我一直把它们混淆。
- 最长公共子串举例：假设S1={A,D,C,B,E,X,Q}，S2={H,P,D,C,B,E,M,L}
那么它们的最长公共子串就是{D,C,B,E}。这是我通常理解的东西。
最长公共子序列。 - 最长公共子序列举例：假设S1={A,B,C,A,D,A,B}，S2={B,A,C,D,B,A}，那么它们的LCS就是{B,A,D,B}。
求解最长公共子序列
这是一个动态规划问题。如何求解最长公共子序列（以下用LCS代替）呢？我们假设已经知道Z={z1,z2,…zk}是X={x1,x2,…,xm}和Y={y1,y2,…,yn}的LCS，那么可以分以下三种情况讨论（具体每种情况证明不再累述）：
1. xm=yn=zk：那么Zk-1是Xm-1和Yn-1的LCS。
2. xm≠yn，yn≠zk：我们可以把yn去掉，那么Zk是Xm和Yn-1的LCS。
3. xm≠yn，xm≠zk：我们可以把xm去掉，那么Zk是Xm-1和Yn的LCS。
基于以上情况，我们可以得到LCS递归式。我们假设c[i][j]表示Xi和Yi的LCS长度，那么：
- c[i][j]=0(i=0或j=0)；
- c[i][j]=c[i-1]c[j-1]+1(i,j>0且xi=yi）；
- c[i][j]=max{c[i-1][j],c[i],[j-1]}；（i,j>0且xi≠yi）。
这样我们就可以得到LCS的长度。如何得到具体内容是什么呢？我们可以借用一个辅助数组b[i][j]，这个数组用来记录c[i][j]的来源，分别有如下情况：
- c[i][j]=c[i-1][j-1]+1，则b[i][j]=1；
- c[i][j]=c[i][j-1]，则b[i][j]=2；
- c[i][j]=c[i-1][j]，则b[i][j]=3。
这样就可以根据b[m][n]反向追踪LCS，当b[i][j]=1，输出xi；当b[i][j]=2，追踪c[i][j-1]；当b[i][j]=3，追踪c[i-1][j]，直到i=0或j=0停止。
算法设计
（1）初始化。初始化c[][]第1行和第1列为0。
（2）开始操作。具体是将s1[i]分别与s2[j-1]（j=1,2,…,len2）进行比较，若字符相等c[i][j]=左上角数值+1，且b[i][j]=1；若不相等，则c[i][j]等于左侧或者上侧重最大的一个数值，若左侧和上侧相等，则取左侧，且b[i][j]=2或3（当取左侧为2，取上侧为3）。最后的c[][]和b[][]如下所示：
下表是c[][]：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| A | 0 | 1 | 2 | 2 | 2 | 2 | 3 |
| D | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
下表是b[][]：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 2 | 1 | 2 | 2 | 2 | 1 |
| 2 | 0 | 1 | 2 | 2 | 2 | 1 | 2 |
| 3 | 0 | 3 | 2 | 1 | 2 | 2 | 2 |
| 4 | 0 | 3 | 1 | 2 | 2 | 2 | 1 |
| 5 | 0 | 3 | 3 | 2 | 1 | 2 | 2 |
| 6 | 0 | 3 | 1 | 2 | 3 | 2 | 1 |
| 7 | 0 | 1 | 3 | 2 | 3 | 1 | 2 |
根据c[][]可以得出，LCS的长度为4（也就是c[][]最后一个值）。然后开始判断内容是什么，这是要根据b[][]来。
首先，b[7][6]=2，向左找b[7][5]=1，所以向左上角找b[6][4]，得到字母为s1[6]=[B]；
b[6][4]=3，向上找b[5][4]=1，向左上角找b[4][3]，得到字母s1[4]=[D]；
b[4][3]=2，向左找b[4][2=1，向左上角找b[3][1]，得到字母s1[3]=[A]；
b[3][1]=3，向上找b[2][1]=1，向左上角找b[1][0]，得到字母s1[1]=[B].
由于b[1][0]=0，所以算法停止，返回结果为“BADB”。
代码演示
void LCSL()
{
int i, j;
for(i=1;i<len1;i++)
for (j = 1; j < len2; j++)
{
if (s1[i = 1] == s2[j - 1])
{
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else
{
if (c[i][j - 1] >= c[i - 1][j])
{
c[i][j] = c[i][j - 1];
b[i][j] = 2;
}
else
{
c[i][j] = c[i - 1][j];
b[i][j] = 3;
}
}
}
}
void print(int i, int j)
{
if (i == 0 || j == 0)
return;
if (b[i][j] == 1)
{
print(i - 1, j - 1);
cout << s1[i - 1];
}
else if (b[i][j] == 2)
print(i, j - 1);
else
print(i - 1, j);
}
编辑距离
编辑距离和LCS的不同点
- 编辑距离的d[][]取值公式如下：
（一个前提，若xi=yj，则diff=0；否则为1）
d[i][j]=min{d[i – 1][j] + 1, d[i][j – 1] + 1,d[i-1][j-1]+diff} - 构造最优解：编辑距离是从右下角开始，逆向查找d[i][j]的来源：上面表示需要删除，左侧表示需要插入；左上角要判断字符是否相等，若相等，不做任何操作，若不相等，执行替换。
- 两者的时间复杂度都是O(n*m)。
代码实现
int min(int a, int b,int c)
{
int temp = (a < b) ? a : b;
return (temp < c) ? temp : c;
}
//编辑距离函数
int editdistance(char *str1, char *str2)
{
int i, j;
int len1 = strlen(str1);
int len2 = strlen(str2);
for (i = 0; i <= len1; i++)
{
d[i][0] = i;
}
for (j = 0; j <= len2; j++)
{
d[0][j] = j;
}
for (i = 1; i <= len1; i++)
{
for (j = 1; j <= len2; j++)
{
int diff;
if (str1[i - 1] == str2[j - 1])
diff = 0;
else
diff = 1;
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1,d[i-1][j-1]+diff);
}
}
return d[len1][len2];
}
游艇租赁问题
假设在一条河上有n个游艇出租站，游客可以在这些游艇出租站租游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到j之间的租金为r(i,j)，i<=i<=j<=n。设计一个算法，计算从游艇出租站i到出租站j所需要的租金最少。
问题分析
（1）分析最优解的结构特征
（2）简历最优值的递归式
m[i][j]=
0(j=i);
r[i][j];j=i+1;
min{m[i][k]+m[k][j],r[i][j],j>i+1。
算法设计
（1）确定合适的数据结构：采用二维数组r[][]输入数据，二维数组m[][]存放各个子问题的最优值，二维数组s[][]存放各个子问题的最优决策（停靠站点）。
（2）初始化：m[i][j]=r[i][j]，然后再找有没有比m[i][j]小的值，如果有，则记录该最优值和最优解即可，s[i][j]=0.
（3）循环阶段：
- 按照递归关系式计算3个站点i,i+1,j(j=i+2)的最优值，并将其存入m[i][j]，同时将最优策略存入s[i][j]，i=1,2,…,n-2。
- 按照递归关系式计算4个站点i,i+1,i+2,j(j=i+3)的最优值，并将其存入m[i][j]，同时将最优策略存入s[i][j]，i=1,2,…,n-3。
- 以此类推，直到求出n个站点的最优值m[1][n]。
（4）构造最优解。根据s[][]递归构造最优解。s[1][n]是第一个站点到底n个站点）1,2,…,n）的最优解的停靠站点，即停靠了第s[1][n]个站点，我们在递归构造两个子问题(1,2,…,k）和（k,k+1,…,n）的最优解停靠站点，一直递归到只包含一个站点为止。
代码实现
void rent()
{
int i, j, k, d;
for (d = 3; d <= n; d++)
{
for (i = 1; i <= n - d + 1; i++)
{
j = i + d - 1;
for (k = i + 1; k < j; k++)
{
int temp;
temp = m[i][k] + m[k][j];
if (temp < m[i][j])
{
m[i][j] = temp;
s[i][j] = k;
}
}
}
}
}
void print(int i, int j)
{
if (s[i][j] == 0)
{
cout << "-- " << j;
return;
}
print(i, s[i][j]);
print(s[i][j], j);
}
代码实现2：最贵的租金
其实只是把总结的递归式中的j>i+1的时候的min改为了max。所以只是修改了代码中的
if (temp<m[i][j])
将其改为了
if (temp>m[i][j])
快速计算——矩阵连乘
最优递归式：
当i=j时，只有一个矩阵，m[i][j]=0；
当i<j的时候，m[i][j]=min{m[i][k]+m[k+1][j]+pip(k+1)qj}
算法设计
（1）确定合适的数据结构。用一维数组p[]记录矩阵的行和列，第i个矩阵的行数存在数组的第i-1位置，列存在第i位置。二维数组m[][]用来存放各个子问题的最优值，二维数组s[][]来存放各个子问题的最优决策（加括号的位置）。
（2）初始化。m[i][i]=0，s[i][i]=0。
（3）循环阶段。
– 按照递归关系式计算2个矩阵Ai、Ai+1相乘时的最优值，j+i+1，并将其存入m[i][j]；同时将最优策略计入s[i][j]。i=1,2,3,..,n-1。
– 按照递归关系式计算3个矩阵相乘Ai、Ai+1、Ai+2,相乘时的最优值，j+i+2，并将其存入m[i][j]，同时将最优策略记入s[i][j]，i=1,2,3,…,n-2。
– 以此类推，直到求出n个矩阵相乘的最优值m[1][n]。
（4）构造最优解
根据最有决策信息数组s[][]递归构造最优解。s[1][n]表示A1A2…An最优解的加括号位置，我们在递归构造两个子问题的最优解加括号位置，一直低轨道子问题只包含一个矩阵为止。
举例图解
| 矩阵 | A1 | A2 | A3 | A4 | A5 |
|---|---|---|---|---|---|
| 规模 | 3*5 | 5*10 | 10*8 | 8*2 | 2*4 |
（1）初始化
m[i][i]=0,s[i][i]=0
（2）计算两个矩阵相乘的最优值
m[][]如下：
| m[][] | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 150 | 390 | 290 | 314 |
| 2 | 0 | 400 | 260 | 300 | |
| 3 | 0 | 160 | 240 | ||
| 4 | 0 | 64 | |||
| 5 | 0 |
s[][]如下：
| s[][] | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 2 | 1 | 4 |
| 2 | 0 | 2 | 2 | 4 | |
| 3 | 0 | 3 | 4 | ||
| 4 | 0 | 4 | |||
| 5 | 0 |
（3）构造最优解
类似于游艇租赁
代码实现
void matrixchain()
{
int i,j,r,k;
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));
for(r = 2; r <= n; r++) //不同规模的子问题
{
for(i = 1; i <= n-r+1; i++)
{
j = i + r - 1;
m[i][j] = m[i+1][j] + p[i-1] * p[i] * p[j]; //决策为k=i的乘法次数
s[i][j] = i; //子问题的最优策略是i;
for(k = i+1; k < j; k++) //对从i到j的所有决策，求最优值，记录最优策略
{
int t = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
if(t < m[i][j])
{
m[i][j] = t;
s[i][j] = k;
}
}
}
}
}
void print(int i,int j)
{
if( i == j )
{
cout <<"A[" << i << "]";
return ;
}
cout << "(";
print(i,s[i][j]);
print(s[i][j]+1,j);
cout << ")";
}