首页 > 试题广场 >

跳台阶

[编程题]跳台阶
  • 热度指数:1053331 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

数据范围:
要求:时间复杂度: ,空间复杂度:
示例1

输入

2

输出

2

说明

青蛙要跳上两级台阶有两种跳法,分别是:先跳一级,再跳一级或者直接跳两级。因此答案为2       
示例2

输入

7

输出

21
推荐

对于本题,前提只有 一次 1阶或者2阶的跳法。

a.如果两种跳法,1阶或者2阶,那么假定第一次跳的是一阶,那么剩下的是n-1个台阶,跳法是f(n-1);

b.假定第一次跳的是2阶,那么剩下的是n-2个台阶,跳法是f(n-2)

c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) 

d.然后通过实际的情况可以得出:只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

e.可以发现最终得出的是一个斐波那契数列:

        

              | 1, (n=1)

f(n) =     | 2, (n=2)

              | f(n-1)+f(n-2) ,(n>2,n为整数)
public class Solution {
    public int jumpFloor(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else if (target ==2) {
            return 2;
        } else {
            return  jumpFloor(target-1)+jumpFloor(target-2);
        }
    }
}


编辑于 2015-06-17 21:21:45 回复(72)
比较倾向于找规律的解法,f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5,  可以总结出f(n) = f(n-1) + f(n-2)的规律,但是为什么会出现这样的规律呢?假设现在6个台阶,我们可以从第5跳一步到6,这样的话有多少种方案跳到5就有多少种方案跳到6,另外我们也可以从4跳两步跳到6,跳到4有多少种方案的话,就有多少种方案跳到6,其他的不能从3跳到6什么的啦,所以最后就是f(6) = f(5) + f(4);这样子也很好理解变态跳台阶的问题了。
class Solution {
public:
    int jumpFloor(int number) {
        if (number <= 0) {
            return 0;
        }
        if (number == 1) {
            return 1;
        }
        if (number == 2) {
            return 2;
        }
        int first = 1, second = 2, third = 0;
        for (int i = 3; i <= number; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }
};
编辑于 2016-10-25 14:12:25 回复(62)
实际上本题最终结果就是一个斐波那契数列,这个前面很多都提到了,我就不再说。
主要分享一下自己的解题思路,开始步骤就是暴力穷举想找规律,以为是N!,但是很快证明不是,于是在纸上画图
很明显是一个二叉树,虽然不平衡,我在画完左半边之后发现,左边的4的子树其实是5的一个子集,5的为0的链接应该是4+3,这是一个典型的斐波那契情况。。一下就破题了,不过那个变态跳台阶的目前还没有想出来。。
发表于 2017-12-06 17:22:50 回复(0)
class Solution:
    def jumpFloor(self , number: int) -> int:
        # 初始化dp数组
        dp = [0, 1, 2]
        # 遍历生成dp数组
        for i in range(3, number+1):
            dp.append(dp[i-1] + dp[i-2])
        return dp[number]

发表于 2022-07-30 17:13:12 回复(0)
    int jumpFloor(int number) {
        if(1 == number)return 1;
        if(2 == number)return 2;
        int a = 2, b = 1;  
        for(int i = 2; i <number; ++i)
        {
            a = a + b;
            b = a - b;
        }
        return a;
    }

发表于 2022-07-28 22:36:44 回复(1)
public class Solution {
    public int jumpFloor(int target) {
  if(target < 0) {
   throw new IllegalStateException();
  }
  int toFloorOneMethods = 1;
  int toFloorTwoMethods = 2;
  int result = 0;
  if(target == 1) {
   return toFloorOneMethods;
  }
  if(target == 2) {
   return toFloorTwoMethods;
  }
 
  for (int i = 3; i <= target; i++) {
   result = toFloorOneMethods + toFloorTwoMethods;
   toFloorOneMethods = toFloorTwoMethods;
   toFloorTwoMethods = result;
  }
  return result;
    }
}

发表于 2022-07-28 13:42:03 回复(0)
class Solution:
    dp = [1 for i in range(50)]
    def jumpFloor(self , number: int) -> int:
        for i in range(2, number+1):
            self.dp[i] = self.dp[i-1] + self.dp[i-2]
        return self.dp[number]

class Solution:
    def jumpFloor(self , number: int) -> int:
        a, b, c = 1, 1, 1
        for i in range(2, number + 1):
            a = b 
            b = c 
            c = a + b
        return c  
发表于 2022-05-11 15:31:42 回复(0)
 public int jumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
发表于 2022-03-29 11:26:55 回复(0)
export function jumpFloor(number: number): number {
    
    // write code here
    if(number <= 0){
        return 0;
    }
    if(number === 1){
        return 1;
    }
    if(number === 2){
        return 2;
    }
    let first:number = 1,second:number = 2 ,third:number = 0;
    for(let i = 3; i <= number;i++){
        third = first + second;
        first = second;
        second = third;
    }
    return third
}


发表于 2022-02-23 23:12:16 回复(0)
可以用组合数学推导:
1. 如果全只跳一步,则方式有C(number, 0)= 1 种;
2. 如果有1次跳两步,其他都跳一步,则方式有 C(number-1, 1)  种;
3. 如果有 i 次跳两步,其余跳一步,其中 i <= number/ / 2,则方式有 C(number - i , i ) 种;
4. 叠加
import math
class Solution:
    def jumpFloor(self , number: int) -> int:
        # write code here
        n = number // 2
        i = 0
        Sum = 0
        if number == 0:
            return 0
        for i in range(n+1):
            term = math.factorial(number-i) / math.factorial(i) / math.factorial(number-i-i)
            #组合数公式,m+n = number, i<=number/2
            Sum += term
        return int(Sum)
发表于 2022-01-01 22:48:48 回复(0)
使用递归【java】:
1. 假设一共有N阶台阶(N >= 3),共需要M步;
2. 那么上台阶最后一步【即第M步】会有两种情况:①一步一阶【JumpFloor(target - 1)】;②一步两阶【JumpFloor(target - 2)]
3. 到M-1步的时候也同第M步一样有两种情况【一步一阶,一步两阶】;
4. 第一步,和第二步可直接得出答案,分别是1和2
5. 因此,当我们要求M是多少时,只要知道第M步是一步一阶时,剩下的M - 1步的值为多少,在加上第M步是一阶两步时,剩下的M - 1步的值是多少【即 M = JumFloor(target -  1) + JumpFloor(target - 2)】,M - 1步 直到第3步的求法同第M步
public class Solution {
    public int jumpFloor(int target) {
        if(target <= 0)
            return 0;
        else if(target == 1)
            return 1;
        else if(target == 2)
            return 2;
        else
            return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
}



发表于 2021-12-29 09:29:00 回复(0)
我想问下各位大佬,是不是不考虑输入0时为0,也可以通过,我直接傻了
发表于 2021-12-02 15:37:23 回复(0)
//可以跑,但很耗时间(#光速逃离)
public class Solution {
    public int jumpFloor(int target) {
        if(target<=0) return 0;
        if(target<=3) return target;
        return jumpFloor(target-1)+jumpFloor(target-2);
    }
}
发表于 2021-11-29 09:08:36 回复(0)
对于这题,没什么多说的
int[] arr = new int[]{0,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141};
        return arr[target];


发表于 2021-10-08 22:18:24 回复(1)
public class Solution {

    // f(n) = f(n-1) + f(n-2), 代表最后一次跳一步和最后一次跳两步的跳法之和
    // f(1) = 1, f(2) = 2, 注意不要从f(0)开始, f(0)没有意义
    public int jumpFloor(int target) {
        if (target <= 2) {
            return target;
        }
        int pre1 = 2, pre2 = 1, ans = 0;
        for (int i = 3; i <= target; i++) {
            ans = pre1 + pre2;
            pre2 = pre1;
            pre1 = ans;
        }
        return ans;
    }
}

发表于 2021-08-06 09:59:28 回复(0)
class Solution:
    def jumpFloor(self, number):
        if number <= 3:
            return number
        num1, num2 = 2, 3
        for _ in range(number-3):
            num2 += num1
            num1 = num2 - num1
        return num2

发表于 2021-07-31 08:18:04 回复(0)
int jumpFloor(int n) {
    int f1,f2,f3,i;
    f1=f2=1;
    if(n==0||n==1)return n;
    for(i=2;i<=n;i++)
    {
        f3=f1+f2;
        f1=f2;
        f2=f3;
    }
    return f3;
}
发表于 2021-07-24 17:12:57 回复(0)
import java.math.BigDecimal;
public class Solution {
    
    //第一次的解法:暴力破解、去重(如果不用BigDecimal,数字会存不下),效率一般,超高耗内存
    public int jumpFloor(int target) {
        BigDecimal ans = BigDecimal.ZERO;
        for(int i=0; i<=target; i++){
            for(int j=0; j<=target/2+1; j++){
                if(i+2*j==target){
                    BigDecimal n = dfsOrder(BigDecimal.valueOf((long)(i+j)), BigDecimal.valueOf(2), BigDecimal.valueOf(1));
                    if(i>1){
                        n = n.divide(dfsRepeat(BigDecimal.valueOf(i),BigDecimal.ONE,BigDecimal.ONE), 0, BigDecimal.ROUND_DOWN);
                    }
                    if(j>1){
                        n = n.divide(dfsRepeat(BigDecimal.valueOf(j),BigDecimal.ONE,BigDecimal.ONE), 0, BigDecimal.ROUND_DOWN);
                    }
                    ans = ans.add(n);
                }
            }
        }
        return ans.intValue();
    }

    /**
     * 数字的不同的排列结果
     * @param n
     * @return
     */
    public BigDecimal dfsOrder(BigDecimal n, BigDecimal start, BigDecimal ans){
        if(start.compareTo(n) > 0){
            return ans;
        }
        ans = start.multiply(ans);
        return dfsOrder(n, start.add(BigDecimal.valueOf(1)), ans);
    }
    //去除重复计算的方式
    public BigDecimal dfsRepeat(BigDecimal num, BigDecimal start, BigDecimal ans){
        if(start.compareTo(num) > 0){
            return ans;
        }
        ans = start.multiply(ans);
        return dfsRepeat(num, start.add(BigDecimal.valueOf(1)), ans);
    }
}
哎..
    //第二种解法 斐波那契数列
    public int jumpFloor(int target) {
        return fibonacci(target, 1, 1);
//         return fibonacci(target);
    }
    
//     //普通递归,效率差,耗内存
//     public int fibonacci(int n){
//         if(n<=1){
//             return 1;
//         }
//         return fibonacci(n-1)+fibonacci(n-2);
//     }
    
    //尾递归,效率高,耗内存
    public int fibonacci(int n, int pre, int curr){
        if(n <= 1){
            return curr;
        }
        return fibonacci(n-1, curr, pre + curr);
    }

//轮询大法
    public int jumpFloor(int target) {
        if(target <= 3){
            return target;
        }
        int pre = 1;
        int curr = 1;
        while(target >= 2){
            int temp = curr;
            curr = pre + curr;
            pre = temp;
            target--;
        }
        return curr;
    }


编辑于 2021-04-18 23:13:58 回复(0)
Python
求解斐波那契数列
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
#         迭代写法
        if number <= 1:
            return number
        pre_n = 0
        n = 1
        for _ in range(number):
            total = pre_n + n
            pre_n = n
            n = total
        return total
#         递归写法 内存溢出
#         if number <= 2:
#             return number
#         return self.jumpFloor(number-1)+self.jumpFloor(number-2)


发表于 2021-04-17 17:50:23 回复(0)
function jumpFloor(number)
{
    // 定义一个数组,用空间换时间
    var tempArr = [,1,2]
    
    // 使用递归,第n个台阶有两种方式,跳一个从n-1跳上来,跳两个从n-2跳上来
    function tempFun (number) {
        if (tempArr[number]) {
            return tempArr[number]
        } else {
            tempArr[number] = tempFun(number - 1) + tempFun(number - 2)
            return tempArr[number]
        }
    }
    return tempFun (number)
}
module.exports = {
    jumpFloor : jumpFloor
};

发表于 2021-04-13 14:55:20 回复(0)
function jumpFloor(number)
{
    // write code here
    var dp = [];
    dp[0] = dp[1] = 1;
    for(var i = 2;i<=number;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[number];
}

发表于 2021-03-16 17:41:26 回复(0)