动态规划

先来看一个问题:

有一座高度是10阶的楼梯,从下往上走,每跨一步可以是一级或两级台阶。要求用程序求出一共一共有多少种走法。

比如,一步一阶,一共10步,这是一种走法。我们可以简写为1,1,1,1,1,1,1,1,1,1。

难画的.png

再比如,每次走两阶,共5步,这是另一种走法。可简写为2,2,2,2,2。

好难画的.png

当然,除此之外,还有很多走法。

容易想到的是利用排列组合的思想,写一个多层嵌套循环遍历出所有可能性,每遍历出一个组合,让计数器加一。

但是这个方法属于暴力枚举,时间复杂度是指数级别的,因此我们想要寻求更高效的解法。

这就是我们的主角动态规划了。先来看看定义:动态规划英文名为Dynamic Programming. 是一种分阶段求解决策问题的数学思想。但它不止用于编程领域,也应用于管理学,经济学,生物学。

是不是听起来高大上但是你还是什么都听不懂啊?

直白点就是一句话:大事化小,小事化了。

拿上面的题目来说,假设只剩最后一步就到达第10阶,这时候会出现几种情况呢?

两种,因为一步走一阶或者两阶,第一种是从第九阶到第十阶,第二种是从第八阶到第十阶。

暂且不管从0到8阶的过程,也不管从0到9阶的过程,想要走到第10阶,一定是从第九阶或者是第八阶开始。

接下来的新问题是:如果已知从0—9阶有X种走法,从0—8阶有Y种走法,那么从0—10阶有多少种走法呢?

没错,就是两部分的总和X+Y。

也就是说:0—10阶走法之和 = 0—8阶走法之和 + 0—9阶走法之和。

方便表达,写为:F(10) = F(9) + F(8)。那么我们怎么求F(9) 和 F(8) 呢?

利用刚才的思路可以推出:F(9) = F(8) + F(7); F(8) = F(7) + F(6)。

惊不惊喜?意不意外?我们正在把一个复杂的问题分阶段进行简化,逐步简化成简单的问题。

而这就是动态规划的思想。

继续上面的问题,当只剩下一阶或者两阶的时候有多少种走法呢?分别是一种和两种。由此,我们归纳出一下公式:

F(1) = 1;

F(2) = 2;

F(n) = F(n-1) + F(n-2);(n>=3)

动态规划中包含三个重要的概念:【最优子结构】、【状态转移公式】、【边界】。

还是上面的例子,我们分析得出F(10) = F(9) + F(8)。 F(9) 和 F(8) 就是F(10) 的最优子结构。

当只有一阶或者两阶台阶时,我们可以直接得出结果,无需继续简化。我们称F(1)和F(2)是问题的【边界】。如果一个问题没有边界,将永远无法得到有限的结果。

F(n) = F(n-1) + F(n-2)是阶段与阶段之间的【状态转移方程】。这是动态规划的核心,决定了问题的每一个阶段和下一个阶段的关系。

(可把我厉害坏了,叉会腰)

叉完腰就会发现:完成的仅仅是动态规划的前半部分:问题建模。下面才是真正麻烦的部分:求解问题。

解法1:前面提到的,递归。既然已经归纳出F(n) = F(n-1) + F(n-2),又知道了递归的结束条件。可以直接用递归实现,代码如下:


int getClimbingWays(int n) {
    if(n < 1) {
        return 0;
    }

    if(n == 1) {
        return 0;
    }

    if(n == 2) {
        return 0;
    }

    return getClimbingWays(n - 1) + getClimbingWays(n - 2);
}

代码比较简单,不做解释。
这样来算确实可以计算出最终答案,氮素让我们来看看它的时间复杂度,首先,递归路径是这样的:要计算F(n),就要先计算F(n - 1) 和 F(n - 2),以此类推

好难画的.png

看起来hin复杂吧,像一颗二叉树吧。
没错,它就是一颗二叉树,树的节点个数就是我们递归方法所需要计算的次数。不难看出,这颗树的高度是N-1,节点个数接近2(n-1),所以方法的时间复杂度可以近似的看作O(2n)。
这效率是极低的,想想有什么可以优化的。
想好没有?没想好就再看看上面的图片,或者直接看下图的相同颜色节点
你没看错,有些相同的参数被重复计算了,而且越往下走,重复的越多(自己往下画画看

非常难画的.png

对于重复计算的情况,应该怎么避免呢?

其中一个方法就是用缓存,先创建一个哈希表,每次把不同参数的计算结果存入哈希,当遇到相同参数时,再直接从哈希 表中取出,就不用重复计算了。我们把这成为备忘录算法。代码如下:

int getClimbingWays(int n, HashMap<Integer,Integer> map) {
    if(n < 1) {
        return 0;
    }

    if(n == 1) {
        return 0;
    }

    if(n == 2) {
        return 0;
    }

    if(map.contains(n)) {
        return map.get(n);
    } else {
        int value = getClimbingWays(n - 1) + getClimbingWays(n - 2);
        map.put(n,value);
        return value;
}

上面代码中,当每次需要计算F(n)时,会首先从map集合中寻找匹配元素。若map中存在,则直接返回结果,若map中不存在,就计算出结果,存入备忘录中。
从F(1)到F(n)一共有n个不同的输入,在哈希表中存了N-2个结果,所以时间可空间复杂度都是O(N)。

下面再来看空间上的优化。能不能把空间复杂度进一步减小呢?

| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
| --------- |-----: | :----: |
|走法数 |1 | 2|||||||||
就让我们用这一张表格阐述奥义:表格上所表示的是已经确定的对应台阶数的走法数。

| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1 | 2|3||||||||
第一次迭代,台阶数等于3走法数量是3,介个结果是怎么来的呢?是F(1)和F(2)相加得来的,F(3)只依赖于F(1)和F(2)。

| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1 | 2|3|5|||||||
第二次迭代,台阶数为4时,走法数是5,这是F(2)和F(3)相加得来的,所以F(4)只依赖于F(2)和F(3)。

| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1 | 2|3|5|8||||||

同理,在后续迭代中,F(5)只依赖于F(3)和F(4),F(6)只依赖于F(4)和F(5)……
由此可见,每一次迭代过程中,只要保留之前的两个状态,就可以推导出新的状态。而不用像备忘录算法那般把全部子状态都记录下来。这才是真正的动态规划的实现

解法3:动态规划实现

int getClimbingWays(int n) {
    if(n < 1) {
        return 0;
    }

    if(n == 1) {
        return 0;
    }

    if(n == 2) {
        return 0;
    }
    
    int a = 1;
    int b = 2;
    int temp = 0;

    for(int i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }

    return temp;
}

程序从i = 3 开始迭代,知道 i = n 结束。每一次迭代,都会计算出多一级台阶的走法数。迭代过程只需要保留两个临时变量 a 和 b,为了便于理解,引入了temp变量,代表了当前迭代的结果值。

现在看起来hin简洁有木有?

再来看看时间空间复杂度。时间复杂度明显的是O(0),由于引入了三个临时变量,所以空间复杂度为O(1)。

这就是动态规划,利用简洁的自底向上的递推方式,实现了时间和空间上的最优化。

氮素,这只是动态规划领域最简单的一道题,因为它只有一个变化维度。

下面给出相对复杂的一道题。
题目:有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?

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

推荐阅读更多精彩内容

  • 回溯算法 回溯法:也称为试探法,它并不考虑问题规模的大小,而是从问题的最明显的最小规模开始逐步求解出可能的答案,并...
    fredal阅读 13,626评论 0 89
  • 动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...
    廖少少阅读 3,256评论 0 18
  • 树形动态规划,顾名思义就是树+DP,先分别回顾一下基本内容吧:动态规划:问题可以分解成若干相互联系的阶段,在每一个...
    Mr_chong阅读 1,464评论 0 2
  • 分治方法 将问题划分成互不相交的子问题 递归地求解子问题 将子问题的解组合起来 动态规划(两个要素:最优子结构、子...
    superlj666阅读 492评论 0 0
  • 六项精进的第五项是"积善行、思利他",稻盛和夫提出"要多行善,多做对他人有益的事",这是做人的根本原则。我们生...
    蓝天白云生产部罗明阅读 252评论 0 0