首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题
  • 热度指数：696049 时间限制：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)
//头像 //

每个台阶都有跳与不跳两种情况（除了最后一个台阶），最后一个台阶必须跳。所以共用2^(n-1)中情况

发表于 2015-06-03 22:36:45 回复(119)
老石基头像 老石基 
public class Solution {
    public int jumpFloorII(int target) {
        if(target<=0)
            return 0;
        return 1<<(target-1);
    }
}

发表于 2016-04-18 14:03:46 回复(0)
加油呀哥们头像 加油呀哥们
class Solution {
public:
    int jumpFloorII(int number) {
/*        //第一种
        long int sum=0;
        if(number==0) return 1;
        else if(number==1) return 1;
        else if(number==2) return 2;
        else
        {
               for(int i=number-1; i>=0; i--)
                   sum += jumpFloorII(i);
        }
        
        return sum;
        */
        //第二种做法
        return pow(2, number-1);
    }
};
发表于 2015-10-09 16:36:30 回复(0)
Yano_nankai头像 Yano_nankai
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
所以f(n)=2*f(n-1)
编辑于 2018-03-28 20:41:06 回复(46)
HXY头像 HXY
一行代码 return  1<<--number;
编辑于 2015-04-25 20:40:41 回复(125)
我的头很铁1头像 我的头很铁1 
public class Solution {
    public int jumpFloorII(int target) {
        int sum=1;
        if(target==0||target==1||target==2)
            return target;
        for(int i=1;i<=target;i++){
            sum+=jumpFloorII(target-i);
        }
        return sum;
    }
}

发表于 2020-02-15 00:35:04 回复(0)
乐天知命头像 乐天知命 
public class Solution {
    public int jumpFloorII(int target) {
        // 假设：f(n)表示：n个台阶第一次1,2,...n阶的跳法数;
        // 若第一次跳了1阶，则还剩n-1阶，
        // 假设：f(n-1)表示：n-1个台阶第一次1,2,...n-1阶的跳法数;
        // 若第一次跳了2阶，则还剩n-2阶，
        // 假设：f(n-2)表示：n-1个台阶第一次1,2,...n-2阶的跳法数;
        // ...
        // 把所以可能的情况（第一次可能跳1,2,...,n阶）加起来：
        // 可以求出：f(n) = f(n-1) + f(n-2) + ... + f(1)
        // 递归：f(n-1) = f(n-2) + ... + f(1)
        // 可以求出：f(n) = 2*f(n-1) 
        
        /*
        if (target <= 0) {
            return 0;
        } else if (target == 1) {
            return 1;
        } else {
            return 2 * jumpFloorII(target - 1);
        }
        */ 
        // 更实用的解法是：从下往上计算，避免了递归的多余计算量
        int a = 1, b = 0;
        if (target <= 0) {
            return 0;
        } else if (target == 1) {
            return 1;
        } else {
            for (int i = 2; i <= target; i++) {
                b = 2 * a;
                a = b;
            }
            return b;
        }
    }
}

编辑于 2017-03-14 01:31:46 回复(0)
Java
王小汪头像 王小汪
可以看做是跳台阶问题的变种。
跳台阶，每次只能跳一个或两个台阶：
dp[i] = dp[i - 1] + dp[i - 2];
每次可以跳任意个：
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4] + ... + dp[1] + 1;
最后+1 表示一步跳到顶。
可以发现规律：
target     res
1            1
2            2
3            2 + 1 + 1 = 4
4            4 + 2 + 1 + 1 = 8
5            8 + 4 + 2 + 1 + 1 = 16
 所以直接返回2的(n - 1)次方就可以了。 
public int jumpFloorII(int target) {
    return 1 << (target - 1);
}




发表于 2022-01-05 00:10:34 回复(0)
Java
匿迹小王子头像 匿迹小王子 
    /**
     * 解题思路：
     * 爬楼梯的变种，爬楼梯只能爬1阶或者2阶，所以需要x(n) = x(n-1)+x(n-2)
     * 那么能跑n阶，是不是意味着x(n) = x(n-1) + x(n-2) + x(n-3) + ... x(0)
     *
     * @author freedom wang
     * @date 2021-01-23 10:29:30
     */
    public int jumpFloorII(int target) {
        if (target == 0 || target == 1) {
            return 1;
        }

        int[] array = new int[target + 1];
        array[0] = 1;
        array[1] = 1;

        for (int i = 2; i < target + 1; i++) {
            int count = 0;
            for (int j = 0; j < i; j++) {
                count += array[j];
            }
            array[i] = count;
        }

        return array[target];
    }
发表于 2021-01-23 10:37:56 回复(0)
OOMError头像 OOMError

得出规律后，直接使用2的n-1次方公式。

public class Page79 {
    public int jumpFloorII(int target) {
        if (target == 0) {
            return 0;
        } else{
            return (int) Math.pow(2,target - 1);
        }
    }

    public static void main(String[] args) {
        Page79 page79 = new Page79();
        System.out.println(page79.jumpFloorII(3));
    }
}
发表于 2019-01-22 11:02:44 回复(0)
Howie59头像 Howie59 
public class Solution {
    public int jumpFloorII(int target) {
        int sum = 1;
        while(target > 1){
            sum *= 2;
            target--;
        }
        return sum;
    }
}
或者是使用位运算
发表于 2018-08-03 11:55:29 回复(0)
山找海味头像 山找海味
class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<(number-1);
    }
};
发表于 2017-10-20 22:57:26 回复(0)
牛客382781号头像 牛客382781号
当target等于1时，有1种跳法1<<--1
target=2时，有2种跳法1<<--2
target=3时，有4种跳法1<<--3
target=4时，有8中跳法1<<--4
.....
return 1<< -- target，所以这一句代码即可
发表于 2015-10-01 17:06:20 回复(0)
最后的最后的最后头像 最后的最后的最后
这不是一个编程逻辑题，其实就是一个数学归纳法罢了！最后可以推出这是一个首项是1，公比为2的等比数列！ 
public int jumpFloorPlus(int target) {
    if(target == 0)
      return 0;
    if(target == 1)
      return 1;
    return 2*jumpFloorPlus(target-1);
  }

发表于 2017-12-27 21:22:46 回复(0)
先扯头像 先扯 
这道题如果用递归去解的话，可能时间会超时，感觉每次用递归解都很容易造成大量的冗余数据。所以个人觉得用动态规划比较好。
首先分析题干无非就是找规律。f(n)=f(n-1)+...f(0)
用个长度为target的数组，利用上边的规律，a[target-1]项即为题目答案。
public int jumpFloorII(int target) {
		if (target == 1)
			return 1;
		if (target == 2)
			return 2;
		int a[] = new int[target];
		a[0] = 1;
		a[1] = 2;
		for (int i = 2; i < target; i++) {
			int sum = 0;
			for (int j = 0; j < i; j++) {
				sum += a[j];
			}
			a[i] = sum + 1;
		}
		return a[target - 1];

}
发表于 2016-05-27 23:06:55 回复(1)
人民的名义头像 人民的名义 
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number<=0:
            return 0
        else:
            return 2**(number-1)
Python:若有n个台阶，则 跳法为第一下跳1阶剩余台阶的 跳法为f(n-1)，以及第一下跳2节剩余台阶跳法为f(n-2)，以及第一下跳3阶剩余台阶 跳法为f(n-3)，依次类推知道最后一次是一下子全部跳上去，方法为1，因此f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(1)+1，f(1)=1,f(2)=2..f(n)-f(n-1)=f(n-1)因此f(n)=2f(n-1)是等比数列，首项为1，比例 为2，f(n)=2^(n-1)
发表于 2017-10-18 15:25:49 回复(0)
专业陪跑头像 专业陪跑
结题思路:
1.如果是n不好说。我举个列子，n=4。
这里是直接跳到4的方案：
            第一种 青蛙直接跳到4
这里是直接跳到3，然后跳到4的方案：
            第二种 青蛙跳到3->4
这里是直接跳到2，然后跳到4的方案：
            第三种 青蛙跳到2->(4) #我这里为什么括号，是因为这个4，就是第一种青蛙跳的
            第四种 青蛙跳到2->(3->4)#理由同上
可以推出：
直接跳到1，然后跳到4的方案是：
            1->4
            1->(3->4)
            1->(2->(4))
            1->(2->(3->4))
可以找出一个规律。
代码如下：
public int jumpFloorII(int target) {
        if(target==1||target==2)
            return target;
        int i=target;
        int sum=2;
        while(target>2){
            sum=(int) (sum+Math.pow(2, target-2));
            target--;
        }
        return sum;
    }

发表于 2017-10-17 20:17:05 回复(0)
搬一块叫CV的砖头像 搬一块叫CV的砖 
//1级有1种，2级有2种，3级有4种，之后每多一级台阶都有之前的两种走法，n级有2的n-1种跳法
class Solution {
public:
    int jumpFloorII(int number) {
	    int NumberOfSteps=2;
        if(number<=0)
            return -1;
        if(number==1||number==2)
            return number;
        for (int i=3;i<=number;i++){
            NumberOfSteps *= 2;
            
        }
        return NumberOfSteps;
    }
};

发表于 2016-03-18 01:02:22 回复(0)
C++
格里芬吐了头像 格里芬吐了
return 1<<(number - 1);

一眼看 这种就是 级数问题了 一眼看出 2的n-1次方  直接位运算
发表于 2022-05-19 13:38:17 回复(0)
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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

跳台阶扩展问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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