跳台阶

跳台阶

四月 16, 2019

题目描述


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


观察分析

    小青蛙一次可以跳1级，也可以跳2级。当有n级台阶：

  • 第一次跳1级时，跳法的数目就等于剩下的n-1级台阶的跳法数目
  • 第一次跳2级时，跳法数目就等于剩下n-2级台阶的跳法数目。

    所以n级台阶的总跳法数目等于第一次跳1级和第一次跳2级的数目的和，即f(n)=f(n-1)+f(n-2)。我们会发现这其实就是斐波那契数列。但是，当n=0时，f(n)=0；当n=1时，f(n)=1；当n=2时，f(n)=2，所以当n>2时，f(n)=f(n-1)+f(n-2)。代码如下：

class Solution {
public:
    int jumpFloor(int number) {
        
        if(number <= 2){
            return number;
        }
        
        int first = 1;
        int second = 2;
        int res = 0;
        
        for(int i = 3; i <= number; i++){
            res = first + second;
            first = second;
            second = res;
        }
        
        return res;
    }
};

  1. 1. 题目描述
  2. 2. 观察分析