教你十分钟内完爆动态规划类问题

    大三上运筹学时初步接触过动态规划，印象最深的就是狄科斯屈标号法，只不过当时是为了混考试，没想把它当做一种算法，更没想过找到一种普遍的方法来求这种这个最那个最的问题；最近入手了算法导论，专门看了DP这一节，从中悟出些道理，分享出来

    能被内动态规划求解的问题往往都具有最优子结构跟重叠子问题两个特性，而这里的关键点也是难点就在于找到那个子问题，一旦找好了，后面的推导就顺理成章了，子问题的挖掘方法一般分为两类，也是本文要重点介绍的：n-1流和重叠流。其中后者指的是同一个问题被其他的问题多次引用，特点是比较形象，容易看出来，但为了描述这种形象算法会比较复杂，往往都是O(n^3)的时间复杂度，比如说（见下面的分析）;前者是指子问题与原问题在某个变量上就差个1，算法非常简单,一般O(n^2)，但是n到n-1的状态转换过程比较复杂，需要笔和纸，不断的尝试，比如说。

    我们来体会一下上面两种思路下的动态规划求解的过程

矩阵链乘法:重叠流

假设有矩阵链中有一段A[10..20]，分割点在15跟16之间，即（A[10..15]）×（A[16..20]），我们定义A[10..15]为前缀，A[16..20]为后缀，我们可以很明显的发现A[10..15]不仅仅是A[10..20]的前缀，他可以是A[10..21]的前缀，A[10..22]的也行，也可以是任何A[j..15]的后缀（j<10）；A[16..20]也同理，而这个结果就可以多次复用了，达到重叠的目的，最重要的是，A[10..15]为最优解的话，它不影响任何跟它搭配的后缀（前缀），不会说什么A[10..15]的过程中把内存吃光了后缀就不能计算了，这叫做子问题无关性，这也是为什么无权最长路径没有最优解的原因。于是A[10..20]这种结构满足我们对动态规划子问题的要求，设m[i..j]为上面提到的子问题,s[i][j]为子问题对应的分割点，下面给出构造这两个数组的伪代码

for l=2 to n // 子问题的长度
    for i=1 to n
        j=l+i-1
        for k=i to j-1
            tmp=m[i,k]+m[k+1,j]+p(i-1)p(k)p(j)//假设矩阵An为p(n-1)×p(n)
            if tmp < m[i,j]
                m[i,j]=tmp
                s[i,j]=k

最长回文问题：n+1流

假设有一段子串为S[i..j]，那么它跟S[i..j-1]有什么关系呢，答案是没有关系，我们得紧紧的抓住命题——回文：它至少是最后一个元素跟最前一个元素相同，还得i+1，导致的结果就是该回文的半径-1。如果你能敏锐的看到这一点就好办了，设P[i][j]为S[i..j]的最长回文的半径，P[i][j]就是我们要找的符合动态规划标准的子问题

• 如果S[i]==S[j]，则P[i][j]=P[i+1][j-1]+1，

• 如果S[i]！=S[j]，则P[i][j]=max{P[i][j-2]，P[i+2][j]}，

注意到子问题字符串比原问题字符串要短，于是我们以字符串长度维度自底向上的方式求解，定义以S[i]为中点的回文的半径为r[i]，下面给出代码

import java.lang.Math;
public class LongPalindrome{
    public static void main(String[] args){
        String target = args[0];
        int n=target.length();
        int[] radius = new int[n];
        // int[][] sub=new int[n][n]; //就是上面提到的P[i,j]
        for(int l=3;l<=n;l=l+2){
            for(int i=0;i<n&&(i+l-1<n);i++){
                int j=i+l-1;
                if(target.charAt(i)==target.charAt(j)&&radius[(i+j)/2]==l/2-1){
                    // sub[i][j]=sub[i+1][j-1]+1;
                    radius[(i+j)/2]++;
                }else{
                    // sub[i][j]=Math.max(sub[i][j-2],sub[i+2][j]);
                }
            }
        }
        int tarIndex=0;
        for(int i=0;i<n;i++){
            System.out.println("i:"+i+",r:"+radius[i]);
            if(radius[i]>radius[tarIndex])
                tarIndex=i;
        }
    System.out.println("the longest palindrome is:"+target.substring(tarIndex-radius[tarIndex],tarIndex+radius[tarIndex]+1));
    }
}

我们的目的是打印最长回文，sub[i][j]是为了辅助动态规划思路用的，不必写入实际代码里面

基于接缝裁剪的图像压缩：n+1流

给定一副m×n像素彩色图像，它由像素点数组A[m][n]组成，我们希望从每一行删除一个点，且相邻两行删除的点必须位于相邻列or同一列，也就是说删除的点从首行到尾行构成一条接缝，已知每个像素点a[i][j]与周围像素的相似度d[i][j],定义接缝包含的点的相似度之和为该接缝的破坏度，求使得破坏度最低的接缝

命题对相邻两行删除的点有要求，很明显这是属于n+1流的，对于n的状态（即第n行像素），定义P[i][j]为接缝从第一行开始直到到达点a[i][j]时累积产生的破坏度，我们再切到n-1的状态（即第n-1行像素）：有这么一个关系min{P[i-1][j-1],P[i-1][j-1],P[i-1][j+1]}+d[i][j]→P[i][j]，很明显P[i][j]具备子问题的特征，我们只需要自底向上的方式求解P[i][j]即可计算出接缝最低破坏度，同时使用辅助空间R[i][j]保存路过点a[i][j]的最优接缝上一行路过的点，用于从最后一行还原这条接缝，-1代表左相邻，0同列，1右相邻，即可获取接缝路线；下面给出伪代码实现：

for i=1 to m
    for j=1 to n
        if(i==1)
            P[i][j]=d[i][j]
        else
            P[i][j]=min{P[i-1][j-1],P[i-1][j1],P[i-1][j+1]}+d[i][j]
            R[i][j]=minIndex{P[i-1][j-1],P[i-1][j1],P[i-1][j+1]}//返回-1,0,1
print min{P[m][1],P[m][2],P[m][3],.......P[m][n],}//打印最低破坏度
index=k     //已知最优接缝最后一行路过点a[m][k],
for i=m to 1
    print i,index     //打印行列，获取接缝
    index=index+R[m][index]

其实这两个挖掘子问题的方法跟动态规划的两个特点是对应的，重叠流是重叠子问题的抽象体现，用整体——局部的思想看看你定义的子问题，记住重叠的越多代表最终的动态规划解法较原始的暴力破解的算法有更好的复杂度的提升；n-1流则是最优子结构的简单体现：只需将你定义的问题在某个维度上-1得到一个子问题，比较一下跟原问题有什么关系