32个重要算法之动态规划算法

    最近在网上偶然看到了一个关于最重要算法的调查()，这些算法中有些熟悉，有些连听过都没听过。自己感觉对算法还是比较感兴趣，于是想抽些时间简单的实现下。这样既可以对已经知道的东西进行下巩固，又可以学习些新的东西，而且过两天也该开学了，到时候写代码的机会可能就少了，顺便练练手 ，下面进入正文。

我们知道动态规划是求解全局最优解的有效方法，一般来说能用动态规划算法求解的问题具有以下两个显著特称：
        1）具有最优子结构，也就是说可以递归的定义最优解。
        2）这些最优子结构存在很多的重叠，就像递归的求解斐波那契数列一样，会导致很多子问题求解不止一次，这将导致算法复杂度急剧增加。
   
下面结合具体例子进行说明：
       此处选择的问题是编辑距离的求法，所谓的编辑距离，是如下定义的：
       存在两个字符串A和B，对A进行四中操作：copy、delete、insert和replace，将A转换为B，在此过程中所进行的操作代价最小的过程就是编辑距离了。例如字符串algorithm可以经过上面
       所说四中操作转换为altruistic。在进行求解的工程中，我们要对上述四种操作的代价进行定义，要注意的是copy和replace的代价要小于delete和insert，否则的话copy和replace操作都不
       会使用。
   
   下面利用动态规划算法进行求解：
    首先，要找出最优子结构，假设原字符串为x[1,...,i]，目标字符串为y[1,...,j]，编辑距离定义为c[i,j]，于是我们可以得到如下的公式:
                c[i,j] = min{c[i-1,j]+cost(delete),c[i,j-1]+cost(insert),c[i-1,j-1]+cost(x[i]==y[j]?copy:replace)}
    其中cost代表代价。这就是这个问题的最优子结构啦，之所以分成以上几种情况是因为，最优解 c[i,j]的上一步有四种可能，也就是上面所说的四种操作啦。我们可以明显的看到，如果要是
  递归的求解上述问题会出现很多重叠子问题，例如，在递归求解c[i,j]时，我们就得求解四次 c[i-1,j-1]子问题。这也就是动态规划问题的第二个特征啦。
    接下来，通过编程实现。
    我们知道，从另一个方面看，动态规划问题就是一种自底而上填表的过程(dynamic programming中的programming就是用表格求解的意思)。接下来还是以上面的将algorithm转换
  为altruistic为例进行说明。我们以横轴表示altruistic，以纵轴表示algorithm，所填的表格如下：
  
 此处只是为了方便没有自己去画，而是通过程序进行打印而已。此处定义copy代价为1，delete的代价为2，所以第一列 和第一行会是那样。
 下面给出主要的代码：

static const int COPY_COST      = 1;
static const int REPLACE_COST   = 1;
static const int DELETE_COST    = 2;
static const int INSERT_COST    = 2;

enum status{DELETE,INSERT,COPY,REPLACE};

void edit_distance(const std::string src,const std::string des){
    size_t row = src.size();
    size_t col = des.size();
    std::vector<std::vector<size_t> >table(row,std::vector<size_t>(col));
    std::vector<std::vector<status> >condition(row,std::vector<status>(col));
    size_t i=0;
    while(i<row){
        table[i][0] = i*COPY_COST;
        condition[i][0] = COPY;
        ++i;
    }
    size_t j = 1;
    while(j<col){
        table[0][j] = j*DELETE_COST;
        condition[0][j] = DELETE;
        ++j;
    }
    for(i=1;i<row;++i){
        for(j=1;j<col;++j){
            size_t x = table[i][j-1]+INSERT_COST;
            size_t y = table[i-1][j]+DELETE_COST;
            size_t z = table[i-1][j-1] + (src[i]==des[j] ? (COPY_COST) : (REPLACE_COST));
            if(x<y){
                if(x<z){
                    table[i][j]=x;
                    condition[i][j] = INSERT;
                }
                else{
                    table[i][j]=z;
                    condition[i][j] = src[i]==des[j]?COPY:REPLACE;
                }
            }
            else{
                if(y<z){
                    table[i][j]=y;
                    condition[i][j] = DELETE;
                }
                else{
                    table[i][j]=z;
                    condition[i][j] = src[i]==des[j]?COPY:REPLACE;
                }
            }
        }
    }
}

此处列去了如何得到结果的一些列操作，那个是保存在condition中的，只需递归的输出下就可以了 。

参考文献：
 算法导论：192~221
  此文出处：http://blog.chinaunix.net/uid-28311809-id-3874518.html