动态规划算法

动态规划的关键点:

  1. 最优化原理,也就是最优子结构性质。这指的是一个最优化策略具有这样的性质,无论过去状态和决策如何,对前面的决策所形成的状态而言,余下的决策必须构成最优策略,简单来说就是一个最优化策略的子策略总是最优的,如果一个问题满足最优化原理,就称其有最优子结构性质。
  2. 无后效性,指的是某个状态下的决策的收益,只与状态和决策相关,与达到该状态的方式无关。
  3. 子问题的重叠性,动态规划将原来指数级的暴力搜索算法改进到了具有多项式时间复杂度的算法,其中的关键在于解决了冗余、重复计算的问题,这是动态规划算法的根本目的。
  4. 总体来说,动态规划算法就是一系列以空间换取时间的算法。

动态规划使用

下面通过递归方式计算问题斐波那契数列(Fibonacci sequence)来阐述分治法不是银弹

斐波那契数列指的是这样一个数列 0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........


斐波那契数列数学表示

这个数列从第3项开始,每一项都等于前两项之和。
下面给出递归实现的代码:

    /**
     * 求解Fibonacci数列中第n个元素的值
     * @param n 斐波那契数列中的位置
     * @return Fibonacci数列中第n个元素的值
     */
    public int fibonacci(int n) {
        if(n<2) return n;
        if(n>=2) {
            return fibonacci(n-1)+fibonacci(n-2);
        }
        return -1;
    }

通过控制台验证下算法的计算结果和计算用时。

fibonacci 0 is 0                计算用时        0ms
fibonacci 1 is 1                计算用时        1ms
fibonacci 2 is 1                计算用时        0ms
fibonacci 3 is 2                计算用时        0ms
fibonacci 4 is 3                计算用时        0ms
fibonacci 5 is 5                计算用时        0ms
fibonacci 6 is 8                计算用时        0ms
fibonacci 7 is 13               计算用时        0ms
fibonacci 8 is 21               计算用时        0ms
fibonacci 9 is 34               计算用时        0ms
fibonacci 10 is 55              计算用时        0ms
fibonacci 11 is 89              计算用时        0ms
fibonacci 12 is 144             计算用时        0ms
fibonacci 13 is 233             计算用时        0ms
fibonacci 14 is 377             计算用时        0ms
fibonacci 15 is 610             计算用时        0ms
fibonacci 16 is 987             计算用时        0ms
fibonacci 17 is 1597            计算用时        1ms
fibonacci 18 is 2584            计算用时        0ms
fibonacci 19 is 4181            计算用时        0ms
fibonacci 20 is 6765            计算用时        0ms
fibonacci 21 is 10946           计算用时        0ms
fibonacci 22 is 17711           计算用时        0ms
fibonacci 23 is 28657           计算用时        1ms
fibonacci 24 is 46368           计算用时        0ms
fibonacci 25 is 75025           计算用时        1ms
fibonacci 26 is 121393          计算用时        1ms
fibonacci 27 is 196418          计算用时        1ms
fibonacci 28 is 317811          计算用时        3ms
fibonacci 29 is 514229          计算用时        2ms
fibonacci 30 is 832040          计算用时        4ms
fibonacci 31 is 1346269         计算用时        8ms
fibonacci 32 is 2178309         计算用时        11ms
fibonacci 33 is 3524578         计算用时        20ms
fibonacci 34 is 5702887         计算用时        29ms
fibonacci 35 is 9227465         计算用时        46ms
fibonacci 36 is 14930352        计算用时        73ms
fibonacci 37 is 24157817        计算用时        127ms
fibonacci 38 is 39088169        计算用时        186ms
fibonacci 39 is 63245986        计算用时        306ms
fibonacci 40 is 102334155       计算用时        505ms
fibonacci 41 is 165580141       计算用时        816ms
fibonacci 42 is 267914296       计算用时        1298ms
fibonacci 43 is 433494437       计算用时        2110ms
fibonacci 44 is 701408733       计算用时        3423ms
fibonacci 45 is 1134903170      计算用时        5525ms
fibonacci 46 is 1836311903      计算用时        9013ms
fibonacci 47 is -1323752223     计算用时        14382ms

可以看出,n=47是出现了int类型的越界(Integer.MAX_VALUE is 2147483647)这里需要注意,计算用时达到了恐怖的14秒多。斐波那契数列的值随着增大进行指数级的增长,运行事件也是指数级的增长(n越大越能看出这一点)。


斐波那契数列-递归方法调用过程

动态规划版本

正如鲁迅先生的《狂人日记》中,孔乙己"回"字的四种写法。动态规划算法有两种等价的实现方法。

  1. 带备忘的自顶向下法(top-down with memoization),此方法仍按自然的递归形式编写过程,但过程会保存每个子问题的解(通常保存在一个数组或者散列表中)。当需要一个子问题的解时,过程首先检查是否已经保存过此解。如果是,则直接返回保存的值,从而节省了计算时间,否则,按通常的方式计算这个子问题。我们称这个递归过程是带备忘的(memoized),因为它“记住”了之前计算出的结果。
    以斐波那契数列的解法为例,代码如下:
    long[] memo=new long[memoSize];
    public long topdown(int n) {
        if(n<0) return -1;
        if(n<2) return n;
        if(memo[n]>0) {
            return memo[n];
        }else {
            return memo[n]=topdown(n-1)+topdown(n-2);
        }

通过控制台验证下算法的计算结果和计算用时。

fibonacci 0 is 0        计算用时        0ms
fibonacci 1 is 1        计算用时        0ms
fibonacci 2 is 1        计算用时        0ms
fibonacci 3 is 2        计算用时        1ms
fibonacci 4 is 3        计算用时        0ms
fibonacci 5 is 5        计算用时        0ms
fibonacci 6 is 8        计算用时        0ms
fibonacci 7 is 13       计算用时        0ms
fibonacci 8 is 21       计算用时        0ms
fibonacci 9 is 34       计算用时        0ms
fibonacci 10 is 55      计算用时        0ms
fibonacci 11 is 89      计算用时        0ms
fibonacci 12 is 144     计算用时        0ms
fibonacci 13 is 233     计算用时        0ms
fibonacci 14 is 377     计算用时        0ms
fibonacci 15 is 610     计算用时        0ms
fibonacci 16 is 987     计算用时        0ms
fibonacci 17 is 1597        计算用时        0ms
fibonacci 18 is 2584        计算用时        0ms
fibonacci 19 is 4181        计算用时        0ms
fibonacci 20 is 6765        计算用时        0ms
fibonacci 21 is 10946       计算用时        0ms
fibonacci 22 is 17711       计算用时        0ms
fibonacci 23 is 28657       计算用时        0ms
fibonacci 24 is 46368       计算用时        0ms
fibonacci 25 is 75025       计算用时        0ms
fibonacci 26 is 121393      计算用时        0ms
fibonacci 27 is 196418      计算用时        0ms
fibonacci 28 is 317811      计算用时        0ms
fibonacci 29 is 514229      计算用时        0ms
fibonacci 30 is 832040      计算用时        0ms
fibonacci 31 is 1346269     计算用时        0ms
fibonacci 32 is 2178309     计算用时        0ms
fibonacci 33 is 3524578     计算用时        0ms
fibonacci 34 is 5702887     计算用时        0ms
fibonacci 35 is 9227465     计算用时        0ms
fibonacci 36 is 14930352        计算用时        0ms
fibonacci 37 is 24157817        计算用时        0ms
fibonacci 38 is 39088169        计算用时        0ms
fibonacci 39 is 63245986        计算用时        0ms
fibonacci 40 is 102334155       计算用时        0ms
fibonacci 41 is 165580141       计算用时        0ms
fibonacci 42 is 267914296       计算用时        0ms
fibonacci 43 is 433494437       计算用时        0ms
fibonacci 44 is 701408733       计算用时        0ms
fibonacci 45 is 1134903170      计算用时        0ms
fibonacci 46 is 1836311903      计算用时        0ms
fibonacci 47 is 2971215073      计算用时        0ms

  1. 自底向上法(bottom-up method),这种方法一般需要恰当定义子问题的“规模”的概念,使得任何子问题的求解只依赖“更小的”子问题的求解。因而我们可以将子问题按规模排序,按由小到大的顺序进行求解。当求解某个子问题时,它所依赖的那些更小的子问题都已经求解完毕,结果已经保存。每个子问题只需求解依次,当我们求解它(也是第一次遇到它)时,它的所有前提子问题都已求解完成。

动态规划的解法-自底向上法

    long[] memo=new long[memoSize];
    public long     bottomup(int n) {
        if(n<0) return -1;
        if(n<=1) return n;
        memo[0]=0;
        memo[1]=1;
        if(n>1) {
            for(int i=2;i<=n;i++) {
                memo[i]=memo[i-1]+memo[i-2];
            }
        }
        return memo[n];
    }

通过控制台验证下算法的计算结果和计算用时。

fibonacci 0 is 0        计算用时        0ms
fibonacci 1 is 1        计算用时        0ms
fibonacci 2 is 1        计算用时        0ms
fibonacci 3 is 2        计算用时        0ms
fibonacci 4 is 3        计算用时        0ms
fibonacci 5 is 5        计算用时        0ms
fibonacci 6 is 8        计算用时        0ms
fibonacci 7 is 13       计算用时        0ms
fibonacci 8 is 21       计算用时        0ms
fibonacci 9 is 34       计算用时        0ms
fibonacci 10 is 55      计算用时        0ms
fibonacci 11 is 89      计算用时        0ms
fibonacci 12 is 144     计算用时        0ms
fibonacci 13 is 233     计算用时        0ms
fibonacci 14 is 377     计算用时        0ms
fibonacci 15 is 610     计算用时        0ms
fibonacci 16 is 987     计算用时        0ms
fibonacci 17 is 1597        计算用时        0ms
fibonacci 18 is 2584        计算用时        0ms
fibonacci 19 is 4181        计算用时        0ms
fibonacci 20 is 6765        计算用时        0ms
fibonacci 21 is 10946       计算用时        0ms
fibonacci 22 is 17711       计算用时        0ms
fibonacci 23 is 28657       计算用时        0ms
fibonacci 24 is 46368       计算用时        0ms
fibonacci 25 is 75025       计算用时        0ms
fibonacci 26 is 121393      计算用时        0ms
fibonacci 27 is 196418      计算用时        0ms
fibonacci 28 is 317811      计算用时        0ms
fibonacci 29 is 514229      计算用时        0ms
fibonacci 30 is 832040      计算用时        0ms
fibonacci 31 is 1346269     计算用时        0ms
fibonacci 32 is 2178309     计算用时        0ms
fibonacci 33 is 3524578     计算用时        0ms
fibonacci 34 is 5702887     计算用时        0ms
fibonacci 35 is 9227465     计算用时        0ms
fibonacci 36 is 14930352        计算用时        0ms
fibonacci 37 is 24157817        计算用时        0ms
fibonacci 38 is 39088169        计算用时        0ms
fibonacci 39 is 63245986        计算用时        0ms
fibonacci 40 is 102334155       计算用时        0ms
fibonacci 41 is 165580141       计算用时        0ms
fibonacci 42 is 267914296       计算用时        0ms
fibonacci 43 is 433494437       计算用时        0ms
fibonacci 44 is 701408733       计算用时        0ms
fibonacci 45 is 1134903170      计算用时        0ms
fibonacci 46 is 1836311903      计算用时        0ms
fibonacci 47 is 2971215073      计算用时        0ms

总结

同样规模的斐波那契数列的计算问题,动态规划版本的都能在很短的时间内计算完毕,递归的解决方案,在小于50的情况下就出现了十几秒的计算情况,动态规划的运行时间的提升很明显。

动态规划解决走台阶问题

有n级台阶,每次上一级或者两级,问有多少种走完n级台阶的方法。

分析:动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出 实际问题。在这个问题上,我们让f(n)表示走上n级台阶的方法数。
那么当n为1时,f(n) = 1,n为2时,f(n) =2,就是说当台阶只有一级的时候,方法数是一种,台阶有两级的时候,方法数为2。那么当我们要走上n级台阶,必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步,所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2),我们用dp[n]来表示动态规划表,dp[i],i>0,i<=n,表示到达i级台阶的方法数。

动态规划的解法-自底向上法

    long[] memo=new long[memoSize];
    public long stepBottomup(int n) {
        if(n<0) return 0;
        if(n==1) return 1;
        if(n==2) return 2;

        memo[0]=1;
        memo[1]=2;
        if(n>1) {
            for(int i=2;i<n;i++) {
                memo[i]=memo[i-1]+memo[i-2];
            }
        }
        return memo[n-1];

    }

通过控制台验证下算法的计算结果和计算用时。

走台阶方案数      楼梯数 1    走法 is 1        计算用时        0ms
走台阶方案数      楼梯数 2    走法 is 2        计算用时        0ms
走台阶方案数      楼梯数 3    走法 is 3        计算用时        0ms
走台阶方案数      楼梯数 4    走法 is 5        计算用时        0ms
走台阶方案数      楼梯数 5    走法 is 8        计算用时        0ms
走台阶方案数      楼梯数 6    走法 is 13       计算用时        0ms
走台阶方案数      楼梯数 7    走法 is 21       计算用时        0ms
走台阶方案数      楼梯数 8    走法 is 34       计算用时        0ms
走台阶方案数      楼梯数 9    走法 is 55       计算用时        0ms
走台阶方案数      楼梯数 10   走法 is 89       计算用时        0ms
走台阶方案数      楼梯数 11   走法 is 144      计算用时        0ms
走台阶方案数      楼梯数 12   走法 is 233      计算用时        0ms
走台阶方案数      楼梯数 13   走法 is 377      计算用时        0ms
走台阶方案数      楼梯数 14   走法 is 610      计算用时        0ms
走台阶方案数      楼梯数 15   走法 is 987      计算用时        0ms
走台阶方案数      楼梯数 16   走法 is 1597     计算用时        0ms
走台阶方案数      楼梯数 17   走法 is 2584     计算用时        0ms
走台阶方案数      楼梯数 18   走法 is 4181     计算用时        0ms
走台阶方案数      楼梯数 19   走法 is 6765     计算用时        0ms
走台阶方案数      楼梯数 20   走法 is 10946        计算用时        0ms
走台阶方案数      楼梯数 21   走法 is 17711        计算用时        0ms
走台阶方案数      楼梯数 22   走法 is 28657        计算用时        0ms
走台阶方案数      楼梯数 23   走法 is 46368        计算用时        0ms
走台阶方案数      楼梯数 24   走法 is 75025        计算用时        1ms
走台阶方案数      楼梯数 25   走法 is 121393       计算用时        0ms
走台阶方案数      楼梯数 26   走法 is 196418       计算用时        0ms
走台阶方案数      楼梯数 27   走法 is 317811       计算用时        0ms
走台阶方案数      楼梯数 28   走法 is 514229       计算用时        0ms
走台阶方案数      楼梯数 29   走法 is 832040       计算用时        0ms
走台阶方案数      楼梯数 30   走法 is 1346269      计算用时        0ms
走台阶方案数      楼梯数 31   走法 is 2178309      计算用时        0ms
走台阶方案数      楼梯数 32   走法 is 3524578      计算用时        0ms
走台阶方案数      楼梯数 33   走法 is 5702887      计算用时        0ms
走台阶方案数      楼梯数 34   走法 is 9227465      计算用时        0ms
走台阶方案数      楼梯数 35   走法 is 14930352     计算用时        0ms
走台阶方案数      楼梯数 36   走法 is 24157817     计算用时        0ms
走台阶方案数      楼梯数 37   走法 is 39088169     计算用时        0ms
走台阶方案数      楼梯数 38   走法 is 63245986     计算用时        0ms
走台阶方案数      楼梯数 39   走法 is 102334155        计算用时        0ms
走台阶方案数      楼梯数 40   走法 is 165580141        计算用时        0ms
走台阶方案数      楼梯数 41   走法 is 267914296        计算用时        0ms
走台阶方案数      楼梯数 42   走法 is 433494437        计算用时        0ms
走台阶方案数      楼梯数 43   走法 is 701408733        计算用时        1ms
走台阶方案数      楼梯数 44   走法 is 1134903170       计算用时        0ms
走台阶方案数      楼梯数 45   走法 is 1836311903       计算用时        0ms
走台阶方案数      楼梯数 46   走法 is 2971215073       计算用时        0ms
走台阶方案数      楼梯数 47   走法 is 4807526976       计算用时        0ms

这里只给出其中的一种解法,至于另一种解法,大家尝试的写下。

以上,谢谢阅读,希望你有所收获!

算法导论公开课笔记(一)算法分析与设计
算法导论公开课笔记(二)快速排序和随机化算法
算法导论公开课笔记(三)线性时间排序
算法导论公开课笔记(四)顺序统计、中值
动态规划算法

参考链接
动态规划算法经典案例

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容

  • 原文: 常用的算法设计思想主要有动态规划、贪婪法、随机化算法、回溯法等等,这些思想有重叠的部分,当面对一个问题的时...
    josephok阅读 1,107评论 0 3
  • 动态规划学习-无资料 理论解释http://www.cnblogs.com/steven_oyj/archive/...
    RavenX阅读 1,020评论 0 2
  • 基本概念 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,...
    羽恒阅读 313评论 0 1
  • 动态规划 动态规划算法, Dynamic Programming简称DP,通常基于一个递推公式及一个或多个初始状态...
    御风逍遥阅读 5,277评论 0 7
  • 对没错,今天我又分手了。每次分手都是一样,因为小事吵得不可开交直至分手。真的挺累的,但我没想到她不觉得我好过,这可...
    Lademon阅读 180评论 0 0