必威体育Betway必威体育官网
当前位置:首页 > IT技术

动态规划--台阶问题

时间:2019-07-24 02:12:21来源:IT技术作者:seo实验室小编阅读:83次「手机版」
 

台阶

有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

如果每次走1级,需要走10步,结果可以表示成(1,1,1,1,1,1,1,1,1,1);

如果每次走2级,需要走5步,结果可以表示成(2,2,2,2,2,);

思考一下,你还能写出几种……

那么,共有多少种走法呢?

我们可以这样想,假设我们现在还有最后一步要走,可能的情况有哪些?

1.我们站在第9级上,一步1级后到达顶端;

2.我们站在第8级上,一步2级后到达顶端;

所以,最后一步可以走1级或者2级,不外乎两种情况。

再假设,已知从0级到9级的走法有M种,从0级到8级的走法有N种,那么思考一下,从0到10级的走法和M、N有什么关系呢?从0到10级的走法一共是多少种呢?答案是M+N。

也就是说,用F(n)来表示从0级到n级的走法,可得出

F(9)=M;

F(8)=N;

F(10)=M+N;

F(10)=F(9)+F(8);

如果已知从0到9级的走法和从0到8级的走法,问题就有答案了,那从0级到9级的走法有多少种呢?

我们依然这样想,还有一步就到9级,可能的情况有两种,从8到9和从7到9,已知了从0级到8级的走法有N种,如果再知道从0到7的走法有P种,那么从0到9级的走法就是N+P,那么可得出

F(8)=N;

F(7)=P;

F(9)=N+P;

F(9)=F(8)+F(7);

把一个复杂的问题,逐步简化成简单的问题,我们继续推断,当只剩下2级台阶和1级台阶时的走法分别是2和1。不难归纳出:

F(1)=1;

F(2)=2;

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

这是一个递归,有了公式和递归结束条件,就可以写出程序了。

方法一:递归

 

public int getResultByRecursion(int n){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        return getResultByRecursion(n-1) + getResultByRecursion(n-2);
    }

当n=30时的结果:

时间复杂度2的n次方

没错,这是一棵二叉树,如图所示,这里同样颜色的表示重复计算的节点,而且多数都不止重复计算了一次。我们可以对此进行优化,使用哈希表存储已经计算的节点,不再重复计算。

方法二:备忘录算法

public int getResultByMap(int n, Map<integer,Integer> map){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        if(map.containsKey(n)){
            return map.get(n);
        }else{
            int value = getResultByMap(n-1,map) + getResultByMap(n-2,map);
            map.put(n,value);
            return value;
        }
    }

当n=30时的结果:

时间复杂度和空间复杂度都为O(n)。其实,我们无非使用了空间换时间,但这里很多节点不用保存,比如说,我们自底向上地来考虑这个问题,n为1和2时是显而易见的,当n=3时,可通过1和2的结果来得出,当n=4时,可通过2和3的结果来得出,我们只需要保存最近的两个结果就可以了。所以,还可以进一步优化。

方法三:动态规划

public int getResultByDP(int n){
        if (n <1) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }

        int a = 1;
        int b = 2;
        int temp = 0;

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

时间复杂度为O(n),空间复杂度为O(l)。

总结:动态规划是一种解决复杂问题的方法,它将大问题分成小问题或者说子问题,这些子问题是独立的,且会有重叠,也就是各子问题包含公共的子子问题,动态规划不会重复地求解公共子问题,而是对每个子问题只求解一次,将结果保存起来,从而避免每次遇到各个子问题时重新计算结果。适合采用动态规划方法的最优化问题中的两个要素:最优子结构和重叠子问题。

如果问题的一个最优解中包含了子问题的最优解,那么该问题具有最优子结构。在上面的问题中,F(10)=F(9)+F(8),所以F(9)和F(8)是F(10)的最优子结构。用来求解原问题的递归算法可反复地解同样的子问题,而不是总在产生新的子问题,对两个子问题来说,如果它们确实是相同的子问题,只是作为不同问题的子问题出现的话,则它们是重叠的。

相关阅读

网赚靠不靠谱?老司机用真实经历回答这个问题

在所有的兼职工作中,网赚是一种普遍受到大家欢迎的赚钱方法,不管是大学生还是全职妈妈,只要会用电脑基本上都能赚到钱。但是,很多初次

01背包问题,最良心的讲解了

1、动态规划(DP)动态规划(Dynamic Programming,DP)与分治区别在于划分的子问题是有重叠的,解过程中对于重叠的部分只要求解一次,记录下结

味全每日c支付宝AR红包活动如何参与?相关问题介绍!

大家都知道支付宝的ar功能吧,去年的时候,该功能就比较的火爆,现在有了一种新的玩法,那就是味全每日c支付宝AR红包活动,每个支付宝用户

U盘插上,系统有反应,但是却不识别,电脑能识别其他的U盘,U

问题描述: 1.U盘插上,系统有反应,但是却不识别,绝大多数是驱动的问题: 解决办法: 将U盘插在电脑上,控制面板-设备管理器-通用穿行总线控

1111购物狂欢节淘宝卖家常见问题

随着2012年11月11日即将临近,好多淘宝的卖家在论坛上提问了关于“1111购物狂欢节”的问题,(点此进入“双十一”主会场)下面seo实验室

分享到:

栏目导航

推荐阅读

热门阅读