首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题
  • 热度指数：691807 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围：
进阶：空间复杂度 ， 时间复杂度
示例1

输入

3

输出

4
示例2

输入

1

输出

1
算法知识视频讲解
添加回答
推荐
dangle头像 dangle

关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:

f(1) = 1

f(2) = f(2-1) + f(2-2)         //f(2-2) 表示2阶一次跳2阶的次数。

f(3) = f(3-1) + f(3-2) + f(3-3) 

...

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 

 

说明： 

1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。

2）n = 1时，只有1种跳法，f(1) = 1

3) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2) 

4) n = 3时，会有三种跳得方式，1阶、2阶、3阶，

    那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)

    因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

5) n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：

    f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)

    

6) 由以上已经是一种结论，但是为了简单，我们可以继续简化：

    f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

    f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

    可以得出：

    f(n) = 2*f(n-1)

    

7) 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：

              | 1       ,(n=0 ) 

f(n) =     | 1       ,(n=1 )

              | 2*f(n-1),(n>=2)
public class Solution {
    public int jumpFloorII(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else {
            return 2 * jumpFloorII(target - 1);
        }
    }
}

编辑于 2015-06-17 21:30:40 回复(217)
Python
offer多多小能手头像 offer多多小能手 
class Solution:
    def jumpFloorII(self, number):
        # write code here
        res = [0,1,2]
        while len(res) <= number:
            res.append(sum(res)+1)
        return res[number]

发表于 2021-12-04 17:16:50 回复(0)
Python
阿司匹林Yo头像 阿司匹林Yo 
class Solution:
    def jumpFloorII(self, number):
        if number == 1:
            return 1
        res = 1
        for i in range(1, number):
            res += self.jumpFloorII(number-i)
        return res

发表于 2021-07-31 08:47:14 回复(0)
Python
弱鸡来学习头像 弱鸡来学习
顺着官方的优化思路
f[n-1] = 2 * f[n-2]
因此
f[n] = 2 * 2 * f[n-2]
.
.
.
f[n] = 2**(n-1)* f[1]
又因为：
f[1] = 1
f[n] = 2 **(n-1)

发表于 2021-06-24 22:49:01 回复(0)
Python
wengJJ头像 wengJJ
Python
f(n) = 2f(n-1) 递归解千愁 
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number == 0 or number == 1:
            return number
        return 2 * self.jumpFloorII(number-1)


编辑于 2021-06-12 01:46:07 回复(0)
Python
两个头一个大头像 两个头一个大
# -*- coding:utf-8 -*-
# 根据官方思路写的
class Solution:
    def jumpFloorII(self, number):
        # write code here
        fib = [1, 1]
        for i in range(1, number):
            fib.append(sum(fib[:]))
        return sum(fib[:-1])
发表于 2021-06-03 14:59:00 回复(0)
Python
子衿~头像 子衿~

一行代码得到结果。解题思路如下：

青蛙最终要到第n个台阶，在前面的n-1的台阶都可以选择踏或者跳过去。于是n-1台阶，有2**(n-1) 种方式。 
# -*- coding:utf-8-*-
classSolution:
    def jumpFloorII(self, number):
        return 2**(number-1)


编辑于 2021-04-30 00:02:42 回复(0)
Python
谁看见我的大白菜了头像 谁看见我的大白菜了
第n层台阶的跳法，等于第n-1层台阶的跳法X2。 
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number <= 1:
            return number
        res = 1
        for i in range(2, number+1):
            res = res * 2
        return res


发表于 2021-02-17 11:09:41 回复(0)
Python
牛客209879436号头像 牛客209879436号 
class Solution:
    def jumpFloorII(self, number):
        # write code here
        y = 2
        if number == 0:
            return None
        if number == 1:
            return 1
        if number == 2:
            return 2
        else:
            for _ in range(number-2):
                y *= 2
        return y
python非递归，f(n) = 2*f(n-1)，还要注意number与循环次数的关系
发表于 2020-11-17 20:23:16 回复(0)
Python
caremore头像 caremore
写了几个台阶，然后找出了规律，就是2**（n-1）
发表于 2020-10-13 15:26:01 回复(0)
Python
牛客513123782号头像 牛客513123782号
python return 2**(number-1)
看了几个大佬的解析，自己有个自己的想法，首先n个阶梯，最后一个一定是落脚点，不如设置落脚点为1，那么相应的非落脚点，即没有踩的阶梯为0，即一个阶梯看做全部的01组合，因此除去最后的一定是1的最后落脚点，一共有n-1个可能是落脚点的位置，也就是一共n-1个01位置，所以排列组合得到2的n-1次幂
发表于 2020-09-12 21:35:11 回复(0)
Python
牛客112527241号头像 牛客112527241号 
class Solution:
    def jumpFloorII(self, number):
        way = [0,1]
        for i in range(2,number+1):
            way.append(sum(way)+1)
        return way[number]

发表于 2020-08-25 12:39:50 回复(0)
Python
lillemon头像 lillemon 
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        return 2**(number-1)


发表于 2020-08-12 21:57:18 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        while number>0:
            return pow(2,number-1)
        return 0    
n=0: 可能组合：0 即0种
n=1:可能组合：1 即1种 2^0
n=2:可能组合：1+1 、2 即2种 2^1
n=3:可能组合：1+1+1、1+2、2+1、3 即4种 2^2
n=4:可能组合：1+1+1+1、1+2+1、1+1+2、2+1+1、2+2、3+1、1+3、4即8种2^3
........
归纳：2^(n-1)种
发表于 2020-07-22 10:31:11 回复(0)
Python
sk8_wt头像 sk8_wt 
# -*- coding:utf-8 -*-
class Solution:
    # 递归（时间复杂度比较高）
    def jumpFloorII(self, number):
        if number <= 1:
            return number
        return self.jump(number)
    def jump(self, number):
        count = 0
        if number == 0:
            return 1
        if number < 0:
            return 0
        for i in range(1,number+1):
            count += self.jump(number - i)
        return count

class Solution:
    # 动态规划（自上而下）
    def jumpFloorII(self, number):
        self.dp = [-1]*(number+1)
        if number <= 1:
            return number
        return self.jump(number)
    def jump(self, number):
        count = 0
        if number == 0:
            return 1
        if number < 0:
            return 0
        if self.dp[number] != -1:
            return self.dp[number]
        for i in range(1,number+1):
            count += self.jump(number - i)
        self.dp[number] = count
        return count
    
class Solution:
    # 动态规划（自下而上）
    def jumpFloorII(self, number):
        if number <= 1:
            return number
        dp = [0]*(number+1)
        dp[0] = 1
        dp[1] = 1
        dp[2] = 2
        for i in range(3,number+1):
            for j in range(i):
                dp[i] += dp[j] 
        return dp[-1]

编辑于 2020-09-07 21:11:19 回复(0)
Python
一直爬的蜗牛头像 一直爬的蜗牛 
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        return pow(2,number - 1)

发表于 2020-05-19 03:22:41 回复(0)
Python
201905242154668头像 201905242154668

变态跳台阶(理论+python实现)

1.理论

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1.1. 数学思想分析

设级台阶有种跳法，根据最后一次跳台阶的数目可以分解为最后一次一级，则前面需要跳级，有种跳法；最后一次跳两级，则前面需要跳级，有种跳法。按照这样的推理，得出以下两条公式：

（注意：有好多网友，这里会漏了加上1，这个1是一次跳n级得到的一种跳法，n-1也是同理，难理解的话，请往后看规律分析法）
f(n)=f(n-1)+f(n-2)+…+f(1)+1


f(n−1)=f(n−2)+f(n-3)+……f(1)+1


为了得到，进行两式相减得通项公式：
f(1)=1
f(n)=2f(n-1)，n>=2，公式1


1.2. 规律分析法

先事先对n=1,2,3,4,5级台阶情况进行分析，点出它们所有可能的跳法，之后观察规律，可以发现它们是呈现以2的幂分布的，可以得出通项公式如下：

同样，也可以根据下面的规律得出公式1的计算式： 



           规律
f(1)=1     2**0
f(2)=2     2**1
f(3)=4     2**2
f(4)=8     2**3
f(5)=16    2**4

python实现

一两行代码即可实现，关键就是分析清楚题目的规律。 

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        #f(1)=1  2**0
        #f(2)=2  2**1
        #f(3)=4  2**2
        #f(4)=8  2**3
        #f(5)=16 2**4
        if number == 0:
            return 0
        return 2**(number-1)
编辑于 2020-02-19 15:13:36 回复(0)
Python
少一块星空头像 少一块星空 
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        return 2 ** (number-1)

发表于 2019-12-26 22:05:49 回复(0)
Python
牛客465985542号头像 牛客465985542号
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.a = 0
        self.b = 1
    def jumpFloorII(self, number):
        # write code here
        if number == 0 | number == 1:
            return number
        for i in range(1,number):
            self.a = 2 * self.b
            self.b = self.a
        return self.a
发表于 2019-12-04 13:10:19 回复(0)
Python
天山剑客头像 天山剑客 
# -*- coding:utf-8 -*-
# 解题思路：动态规划状态转义方程式
# dp[n] = dp[n - 1] + dp[n - 2] + ... + dp[2] + dp[1] + dp[0]
# 第n项为前n项的和（包括0, 0表示n - n, 即跳一次跳上n这种情况），dp[0] == 1
# 总结规律发现dp[n] = 2^ n -1 (n ! = 0)


class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number <= 0:
            return 0
        else:
            return pow(2, number - 1)
                

发表于 2019-11-25 13:28:59 回复(0)
Python
秋水中的鱼头像 秋水中的鱼
用的动态规划,dp[n]=dp[0]+dp[1]+dp[2]+...+dp[n-1]
上第n个台阶的方法数等于前面每一次的次数和
写完以后发现其实dp[i]=dp[i-1]*2
可以优化一下,不用列表,用一个变量sum保存结果,每次还能覆盖 

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number==1:
            return 1
        if number==2:
            return 2
        dp=[0 for i in range(number+1)]
        dp[0]=1
        dp[1]=1
        dp[2]=2
        sum=4
        for i in range(3,number+1):
            dp[i]=sum
            sum+=sum
        return dp[-1]


发表于 2019-10-16 14:54:31 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 递归
来自：开发工程师&系统架构高...
难度：
82条回答 219661浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号