我要招人

去企业版

首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题

热度指数：694022 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

数据范围： $1 \le n \le 20$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(1)$

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

查看答案及解析

推荐

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)

牛客770548236号

//为什么说数学是神
//f(n)=f(n-1)+f(n-2)+...+f(1)
//f(n-1)=f(n-2)+f(n-3)+...+f(1)
//所以f(n)=2f(fn-1)=2^(n-1)直接秒了
int jumpFloorII(int number ) 
{
    if(number ==1)
        return 1;
    return 2*jumpFloorII(number-1);
}

编辑于 2023-12-29 13:52:11 回复(0)

笑笑风格

递推公司：f(n) = 2^(n-1);

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param number int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int jumpFloorII(int number ) {
    // write code here
    return (1 << (number-1));
}

发表于 2022-01-14 20:09:40 回复(0)