首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题
  • 热度指数：696017 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一只青蛙一次可以跳上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)
Javascript
牛客Monica头像 牛客Monica 
// 和上面跳台阶不一样的是，上一题只能跳 1或2级，这一题可以跳1~n级
// res[n] = res[n-1]+...+res[1]+1  //后面这个加1，表示直接跳n级阶梯
// res[n-1] = res[n-2]+...+res[1] +1 //后面这个加1，表示直接跳n级阶梯
function jumpFloorII(number)
{
    // write code here
    let n = number
    if(n===1) return 1
    let res = new Array(n+1).fill(0) //为什么是n+1，因为舍弃0下标（0下标没有意义），而且要保证n个数。
    res[0] = null
    res[1] = 1 //一级台阶只有一种跳法
    
    for(let i = 2 ; i<= n ; i++){ 
        for(let j=1;j<i;j++){     
            res[i] += res[j]
        }
        res[i] += 1 //前面计算的是res[n] = res[n-1]+...+res[1]，最后+1要在这里操作
    }
    return res[n]
}

发表于 2022-05-18 11:23:03 回复(0)
Javascript
nicole27头像 nicole27 
function jumpFloorII(number)
{
    // write code here
    if(number==1){
        return 1
    }else if(number<=0){
        return -1
    }else{
        return 2*jumpFloorII(number-1);
    }
    
}

发表于 2022-03-27 22:32:57 回复(0)
Javascript
AAATest头像 AAATest

动态规划

  1. 确定dp数组意义, 即dp[i]的意义
  2. 确定元素之间的关系, 由题不难发现为 dp[i]为0~i-1的累加
  3. 初始条件, dp[0] = 1 , 第一步只有一种跳跃方式 
    function jumpFloorII(number)
{
 // write code here
 const dp = [1]
 let cur = 1
 while(cur<=number){
     dp[cur] = dp.reduce((sum,num)=>sum+num)
     cur++
 }
 return dp[number]
}
发表于 2022-03-11 21:51:30 回复(0)
Javascript
嘉然今天恰烧烤头像 嘉然今天恰烧烤 
function jumpFloorII(number)
{
    return Math.pow(2,number-1);
}

发表于 2021-10-25 17:40:40 回复(0)
Javascript
JD_fly头像 JD_fly 
function jumpFloorII(number)
{
    // write code here
    return 2**(number-1)
}

发表于 2021-10-06 15:32:09 回复(0)
Javascript
安静点201809191740313头像 安静点201809191740313 
function jumpFloorII(number)
{
    // write code here
    //1、暴力递归，f（0） = 1; f（1） =1; f（n）= 2 * f（n-1）；
//     if(number<=1) {
//         return 1;
//     } else {
//         return 2 * jumpFloorII(number-1);
//     }
    //2、自底向上
    if(number<=1) {
        return 1;
    }
    let fn2=1,sum=0;
    for(let i = 2; i <= number; i++) {
        sum = 2*fn2;
        fn2 = sum;
    }
    return sum;
}

发表于 2021-09-15 02:08:14 回复(0)
Javascript
牛客477650639号头像 牛客477650639号 
function jumpFloorII(number)
{
    // write code here
    if(number === 1) return 1;
    if(number === 2) return 2;
    
    return 2 ** (number-1)
}
module.exports = {
    jumpFloorII : jumpFloorII
};

发表于 2021-08-31 17:31:49 回复(0)
Javascript
十味一心头像 十味一心 
//暴力
function jumpFloorII(number)
{
    // write code here
    if(number<=1) return 1;
    var a = Array.from({ length: number+1 },()=>0);
    a[0]=a[1]=1;
    for(let i=2;i<=number;i++){
        for(let j=0;j<i;j++){
            a[i]+=a[j];
        }
    }
    return a[number];
}
//规律
function jumpFloorII(number)
{
    // write code here
    if(number<=1) return 1;
    var a = Math.pow(2,number-1)
    return a;
}

发表于 2021-08-30 19:47:43 回复(0)
Javascript
titi起飞了头像 titi起飞了
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
 我们都知道跳一层台阶有1种跳法[1]
 跳两层台阶有两种跳法[1,1][2]
 跳三层台阶的跳法[1,2][1,1,1][2,1][3]
 跳4层台阶的跳法[1,2,1][1,1,1,1][2,1,1][3,1][1,1,2][2,2][4][1,3]
跳5层台阶的跳法[1,2,1,1][1,1,1,1,1][2,1,1,1][3,1,1][1,1,2,1][2,2,1][4,1][1,3,1][1,2,2][1,1,1,2][2,1,2][3,2][1,1,3][2,3][1,4]
可以很容易得知 f(0)=0 f(1)=1 f(2)=2 f(3)=1+2+1 f(4)=4+2+1+1
f(n)= f(n-1)+f(n-2)+...f(1)+1
function jumpFloorII(number)
{
      let arr = [0, 1, 2];
      for (let i = 3; i <= number; i++) {
        arr[i] = 0;
        for (let j = 0; j < i; j++) {
          arr[i] += arr[j];
        }
        arr[i] += 1;
      }
    return arr[number]
}
module.exports = {
    jumpFloorII : jumpFloorII
};

发表于 2021-08-03 14:26:49 回复(0)
JavaScript
别卷啦！头像 别卷啦！
function jumpFloorII(number)
{
    // write code here
    if(number == 1) return 1;
    return jumpFloorII(number - 1)*2;
}
发表于 2021-07-04 20:19:27 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function jumpFloorII(number)
{
    // write code here
    if(number == 0 || number == 1){
        return 1;
    }
    var b = 2;
    return Math.pow(b,number - 1);
}

发表于 2021-03-24 18:17:15 回复(0)
JavaScript
好奇的马里奥拒绝内卷头像 好奇的马里奥拒绝内卷 
function jumpFloorII(number)
{
    if(number==1) return 1;
    return 2*jumpFloorII(number-1);
}

发表于 2021-03-16 19:26:27 回复(0)
JavaScript
不进好工作不改名头像 不进好工作不改名
function jumpFloorII(number)
{
    // write code here
    return 1<<(number-1);
}
发表于 2021-03-01 16:21:00 回复(0)
JavaScript
hanCoder头像 hanCoder
问题中青蛙是要跳到第n级台阶，所以第n级台阶一定是存在的，而且青蛙每次可以任意跳几级台阶，所以第n级台阶前面的n-1级台阶都是可存在可不存在的，即前n-1级台阶都有两种情况：存在、不存在。
所以一共存在的情况数为2*(n-1), 
function jumpFloorII(number)
{
    // write code here
    return number>=0 ? Math.pow(2,number-1) : 0;
}


发表于 2021-02-03 11:14:32 回复(0)
JavaScript
jsco0头像 jsco0
我是这样思考的。
每一级台阶，首先可以在上一级的结果上直接添加最后一级台阶，即f(n-1)种。
另外剩下的组合中，将最后一级台阶组合到前面的台阶中，由于要与上面的情况不能重复，所以可以视为将最后一级台阶和前面的某一级台阶绑定在一起计算。绑定在一起后，看做一个台阶。于是也是f(n-1)种。
于是，最后的结果就是2f(n-1)，另外单独判断一下当n=1时即可
发表于 2020-12-06 21:11:41 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

跳台阶扩展问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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