编辑距离

编辑距离和LCS的不同点

1. 编辑距离的d[][]取值公式如下：
   （一个前提，若xi=yj，则diff=0；否则为1）

di=min{

di - 1 + 1, di + 1,di-1+diff}

1. 构造最优解：编辑距离是从右下角开始，逆向查找di的来源：上面表示需要删除，左侧表示需要插入；左上角要判断字符是否相等，若相等，不做任何操作，若不相等，执行替换。
2. 两者的时间复杂度都是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）简历最优值的递归式mi=0(j=i);ri;j=i+1;min{mi+mk,ri,j>i+1。

算法设计

（1）确定合适的数据结构：采用二维数组r[][]输入数据，二维数组m[][]存放各个子问题的最优值，二维数组s[][]存放各个子问题的最优决策（停靠站点）。

（2）初始化：mi=ri，然后再找有没有比mi小的值，如果有，则记录该最优值和最优解即可，si=0.（3）循环阶段：

• 按照递归关系式计算3个站点i,i+1,j(j=i+2)的最优值，并将其存入mi，同时将最优策略存入si，i=1,2,...,n-2。
• 按照递归关系式计算4个站点i,i+1,i+2,j(j=i+3)的最优值，并将其存入mi，同时将最优策略存入si，i=1,2,...,n-3。
• 以此类推，直到求出n个站点的最优值m1。

（4）构造最优解。根据s[][]递归构造最优解。s1是第一个站点到底n个站点）1,2,...,n）的最优解的停靠站点，即停靠了第s1个站点，我们在递归构造两个子问题(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时，只有一个矩阵，mi=0；当i

算法设计

（1）确定合适的数据结构。用一维数组p[]记录矩阵的行和列，第i个矩阵的行数存在数组的第i-1位置，列存在第i位置。二维数组m[][]用来存放各个子问题的最优值，二维数组s[][]来存放各个子问题的最优决策（加括号的位置）。

（2）初始化。mi=0，si=0。（3）循环阶段。

• 按照递归关系式计算2个矩阵Ai、Ai+1相乘时的最优值，j+i+1，并将其存入mi；同时将最优策略计入si。i=1,2,3,..,n-1。
• 按照递归关系式计算3个矩阵相乘Ai、Ai+1、Ai+2,相乘时的最优值，j+i+2，并将其存入mi，同时将最优策略记入si，i=1,2,3,...,n-2。
• 以此类推，直到求出n个矩阵相乘的最优值m1。

（4）构造最优解

根据最有决策信息数组s[][]递归构造最优解。s1表示A1A2...An最优解的加括号位置，我们在递归构造两个子问题的最优解加括号位置，一直低轨道子问题只包含一个矩阵为止。

举例图解

| 矩阵 | A1 | A2 |A3 |A4 |A5

| ------ | ------ | ------ | ------ | ------ | ------ | |规模| 35 | 510 |108 | 82|2*4

（1）初始化

mi=0,si=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 << ")";}