题解 | #跳台阶扩展问题#

跳台阶扩展问题

http://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387

题目难度:简单
题目考察:dp,记忆化搜索,递推
题目内容:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
首先有一题限制了一次可以跳一步或者两步传送门
在那一题状态转移方程为f[i]=f[i-1]+f[i-2]
这一题是可以跳任意步,很容易类比出来f[i]=f[0]+f[1]+f[2]+...+f[i-1],f[0]表示从起点一次跳n步,f[1]表示从第一格一次跳n-1格,以此类推
既然有了递推表达式,所以一定可以用递归来求解
算法1(递归)

class Solution {
public:
    int jumpFloorII(int number) {
        if(number==0)return 1;//终止条件
        int ans=0;
        for(int i=0;i<number;i++)
            ans+=jumpFloorII(i);//f[i]=f[0]+f[1]+f[2]+...+f[i-1]
        return ans;
    }
};

复杂度分析:时间复杂度,每次调用f[n-1],f[n-2],f[n-3]所以时间复杂度为O(n^n)
空间复杂度,没有额外空间,空间复杂度O(1)
可以发现,时间复杂度非常高,同理,可以用记忆化搜索进行优化
算法2(记忆化搜索)

class Solution {
public:
    int f[1001]={0};
            //记录f[n]有没有被搜索过
    int jumpFloorII(int number) {
        if(f[number])return f[number];
            //如果f[n]被搜索过直接返回f[n]
        if(number==0)return 1;//终止条件
        for(int i=0;i<number;i++)
            f[number]+=jumpFloorII(i);
            //f[i]=f[0]+f[1]+f[2]+...+f[i-1]
        return f[number];//返回f[n]
    }
};

复杂度分析:时间复杂度,每个f[i]只会被搜到一次所以时间复杂度为O(n)
空间复杂度,定义了额外空间保存f[n]的值,空间复杂度O(n)
算法3(递推)
观察状态转移方程f[i]=f[0]+f[1]+f[2]+...+f[i-1]
f[i+1]=f[0]+f[1]+f[2]+...+f[i-1]+f[i]=2f[i]
这时即f[i]=2
f[i-1]=2^(n-1)
这时问题就转化为了给一个n求出2^(n-1)
可以采用快速幂优化到O(logn)空间复杂度优化到O(1)
代码如下

class Solution {
public:
    int jumpFloorII(int number) {
        number--;
        int ans=1,a=2;
        while(number)
        {
            if(number&1)ans=ans*a;
            a=a*a;
            number>>=1;
        }
        return ans;
    }
};

时间复杂度O(logn)
空间复杂度O(1)
思考
递推的过程发现了这个问题转化为了2^n-1,但是需要推导,递归方法求dp显得十分清晰,不用推导,加上记忆化搜索使得时间复杂度和空间复杂度都在一个客观的范围内

全部评论

相关推荐

07-25 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
码砖:求职岗位要突出,一眼就能看到,教育背景放到最后,学校经历没那么重要,项目要重点突出
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务