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

逃离我推掉我的手 2024-02-19 20:47 15阅读 0赞

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

关于本题，前提是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) (1)

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

（2）-（1）可以得出：

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

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

| 1 ,(n=0 )

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

| 2\*f(n-1),或者 2^(n-1) (n>=2)

python代码

# -*- coding:utf-8 -*-
    class Solution:
        def jumpFloorII(self, number):
            # write code here
            if number<=1:
                return number
            else:
                return 2**(number-1)

C++代码

class Solution {
    public:
        int jumpFloorII(int number) {
            if(number<=1)
                return number;
            else
                return 2*jumpFloorII(number-1);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

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

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。关于本题，前提是n个台阶会有一次n阶的跳法。分析如下: f(

逃离我推掉我的手/ 2024年02月19日 20:47/ 0 赞/ 16 阅读

相关笔试题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。该题有三种解法：递归的方法求解斐波那契数列、用概率与统计的数学方法解决，３.动态规划

笔试题一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。该题有三种解法：1.递归的方法求解斐波那契数列、2.用概率与统计的数

末蓝、/ 2022年12月24日 12:53/ 0 赞/ 96 阅读

相关剑指Offer——一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

![在这里插入图片描述][20201024121455786.png_pic_center] [详细解答点这个][Link 1] public class Sol

落日映苍穹つ/ 2022年12月17日 15:55/ 0 赞/ 20 阅读

相关 JZ9：(变态跳台阶)一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。过程：乍一看毫无思路。 ![\\ne

た入场券/ 2022年11月26日 08:37/ 0 赞/ 80 阅读

相关 JZ8：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。过程有点类似斐波那契数列。还是

亦凉/ 2022年11月26日 07:58/ 0 赞/ 70 阅读

相关一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。

一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。设：总共有F(n)种跳法

柔光的暖阳◎/ 2022年07月16日 09:43/ 0 赞/ 124 阅读

相关【java】求该青蛙跳上一个n级的台阶总共有多少种跳法

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。台阶数跳法 0 0 1 1 2 2

Bertha 。/ 2022年04月25日 06:10/ 0 赞/ 132 阅读

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

Q：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 A：f(n) = f(n-1)+f(n-2)+…+f(1)

亦凉/ 2022年03月06日 03:22/ 0 赞/ 147 阅读

相关一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

Q：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 A：该问题实质是斐波那契数列求和，递推公式为 f(n)=f(n-1)+f(n-

太过爱你忘了你带给我的痛/ 2022年03月06日 03:18/ 0 赞/ 111 阅读

相关一只青蛙一次可以跳一级或二级台阶，请问跳n级台阶有多少次跳法之斐波那契数列的非递归写法

对于这个问题前三次都好算分别为1,2,3次,后面多的话不好简单计算当第n级台阶时,因为青蛙只能跳一级或二级台阶,所以第n级只有两种方法跳过来,

ゞ浴缸里的玫瑰/ 2022年03月01日 16:22/ 0 赞/ 138 阅读