动态规划小试牛刀–作者:HankingHu 来源:CSDN

--write by zhuwx 2019-06-24 20:58:03 +0800 CST

点击量:55

例题:钢条切割

上面的例题来自于算法导论
关于题目的讲解就直接截图算法导论书上了这里就不展开讲。现在使用一下前面讲到三种方法来来实现一下。 
①递归版本

public static int cut(int []p,int n)
    {
        if(n==0)
            return 0;
        int q=Integer.MIN_VALUE;
        for(int i=1;i<=n;i++)
        {
            q=Math.max(q, p[i-1]+cut(p, n-i));  
        }
        return q;
    }

递归很好理解,如果不懂可以看上面的讲解,递归的思路其实和回溯法是一样的,遍历所有解空间但这里和上面斐波拉契数列的不同之处在于,在每一层上都进行了一次最优解的选择,q=Math.max(q, p[i-1]+cut(p, n-i));这个段语句就是最优解选择,这里上一层的最优解与下一层的最优解相关。

②备忘录版本

public static int cutMemo(int []p)
    {
        int []r=new int[p.length+1];
        for(int i=0;i<=p.length;i++)
            r[i]=-1;                        
        return cut(p, p.length, r);
    }
    public static int cut(int []p,int n,int []r)
    {
        int q=-1;
        if(r[n]>=0)
            return r[n];
        if(n==0)
            q=0;
        else {
            for(int i=1;i<=n;i++)
                q=Math.max(q, cut(p, n-i,r)+p[i-1]);
        }
        r[n]=q;

        return q;
    }

③自底向上的动态规划

public static int buttom_up_cut(int []p)
    {
        int []r=new int[p.length+1];
        for(int i=1;i<=p.length;i++)
        {
            int q=-1;
            //①
            for(int j=1;j<=i;j++)
                q=Math.max(q, p[j-1]+r[i-j]);
            r[i]=q;
        }
        return r[p.length];
    }

自底向上的动态规划问题中最重要的是理解注释①处的循环,这里外面的循环是求r[1],r[2]……,里面的循环是求出r[1],r[2]……的最优解,也就是说r[i]中保存的是钢条长度为i时划分的最优解,这里面涉及到了最优子结构问题,也就是一个问题取最优解的时候,它的子问题也一定要取得最优解。下面是长度为4的钢条划分的结构图。我就偷懒截了个图。

动态规划原理
虽然已经用动态规划方法解决了上面两个问题,但是大家可能还跟我一样并不知道什么时候要用到动态规划。总结一下上面的斐波拉契数列和钢条切割问题,发现两个问题都涉及到了重叠子问题,和最优子结构。

①最优子结构

用动态规划求解最优化问题的第一步就是刻画最优解的结构,如果一个问题的解结构包含其子问题的最优解,就称此问题具有最优子结构性质。因此,某个问题是否适合应用动态规划算法,它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时,用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

②重叠子问题

在斐波拉契数列和钢条切割结构图中,可以看到大量的重叠子问题,比如说在求fib(6)的时候,fib(2)被调用了5次,在求cut(4)的时候cut(0)被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题,不停的调用函数,而不是生成新的子问题。如果递归算法反复求解相同的子问题,就称为具有重叠子问题(overlapping subproblems)性质。在动态规划算法中使用数组来保存子问题的解,这样子问题多次求解的时候可以直接查表不用调用函数递归。

动态规划的经典模型
线性模型
线性模型的是动态规划中最常用的模型,上文讲到的钢条切割问题就是经典的线性模型,这里的线性指的是状态的排布是呈线性的。【例题1】是一个经典的面试题,我们将它作为线性模型的敲门砖。

【例题1】在一个夜黑风高的晚上,有n(n <= 50)个小朋友在桥的这边,现在他们需要过桥,但是由于桥很窄,每次只允许不大于两人通过,他们只有一个手电筒,所以每次过桥的两个人需要把手电筒带回来,i号小朋友过桥的时间为T[i],两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

每次过桥的时候最多两个人,如果桥这边还有人,那么还得回来一个人(送手电筒),也就是说N个人过桥的次数为2*N-3(倒推,当桥这边只剩两个人时只需要一次,三个人的情况为来回一次后加上两个人的情况…)。有一个人需要来回跑,将手电筒送回来(也许不是同一个人,realy?!)这个回来的时间是没办法省去的,并且回来的次数也是确定的,为N-2,如果是我,我会选择让跑的最快的人来干这件事情,但是我错了…如果总是跑得最快的人跑回来的话,那么他在每次别人过桥的时候一定得跟过去,于是就变成就是很简单的问题了,花费的总时间:

T = minPTime * (N-2) + (totalSum-minPTime)

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10,按照上面的公式答案是19,但是实际答案应该是17。

具体步骤是这样的:

第一步:1和2过去,花费时间2,然后1回来(花费时间1);

第二歩:3和4过去,花费时间10,然后2回来(花费时间2);

第三部:1和2过去,花费时间2,总耗时17。

所以之前的贪心想法是不对的。我们先将所有人按花费时间递增进行排序,假设前i个人过河花费的最少时间为opt[i],那么考虑前i-1个人过河的情况,即河这边还有1个人,河那边有i-1个人,并且这时候手电筒肯定在对岸,所以opt[i] = opt[i-1] + a[1] + ai如果河这边还有两个人,一个是第i号,另外一个无所谓,河那边有i-2个人,并且手电筒肯定在对岸,所以opt[i] = opt[i-2] + a[1] + a[i] + 2a2 所以 opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2a[2] }

区间模型
区间模型的状态表示一般为d[i][j],表示区间[i, j]上的最优解,然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解,逐步扩大区间的范围,最终求得[1, len]的最优解。

【例题2】给定一个长度为n(n <= 1000)的字符串A,求插入最少多少个字符使得它变成一个回文串。 典型的区间模型,回文串拥有很明显的子结构特征,即当字符串X是一个回文串时,在X两边各添加一个字符’a’后,aXa仍然是一个回文串,我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数,那么对于A[i] == A[j]的情况,很明显有 d[i][j] = d[i+1][j-1] (这里需要明确一点,当i+1 > j-1时也是有意义的,它代表的是空串,空串也是一个回文串,所以这种情况下d[i+1][j-1] = 0);当A[i] != A[j]时,我们将它变成更小的子问题求解,我们有两种决策:

1、在A[j]后面添加一个字符A[i];

2、在A[i]前面添加一个字符A[j];

根据两种决策列出状态转移方程为:

d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1; (每次状态转移,区间长度增加1)

空间复杂度O(n^2),时间复杂度O(n^2), 下文会提到将空间复杂度降为O(n)的优化算法。

背包模型
背包问题是动态规划中一个最典型的问题之一。由于网上有非常详尽的背包讲解,这里只将常用部分抽出来。

【例题3】有N种物品(每种物品1件)和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。决策为第i个物品在前i-1个物品放置完毕后,是选择放还是不放,状态转移方程为:

f[i][v] = max{ f[i-1][v], f[i-1][v – Ci] +Wi }

时间复杂度O(VN),空间复杂度O(VN) (空间复杂度可利用滚动数组进行优化达到O(V) )。

动态规划题集整理
1、最长单调子序列
Constructing Roads In JG Kingdom★★☆☆☆
Stock Exchange ★★☆☆☆

2、最大M子段和
Max Sum ★☆☆☆☆
最长公共子串 ★★☆☆☆

3、线性模型
Skiing ★☆☆☆☆

总结
弄懂动态规划问题的基本原理和动态规划问题的几个常见的模型,对于解决大部分的问题已经足够了。希望能对大家有所帮助,转载请标明出处http://write.blog.csdn.net/mdeditor#!postId=75193592,创作实在不容易,这篇博客花了我将近一个星期的时间。

参考文献

1.算法导论

作者:HankingHu
来源:CSDN
原文:https://blog.csdn.net/u013309870/article/details/75193592
版权声明:本文为博主原创文章,转载请附上博文链接!