剑指offer-跳台阶

本文为剑指 offer 系列第十篇。
主要内容其实还是斐波那契数列，依旧是上一篇斐波那契的思路，再复习一遍。

题目描述

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

解题思路

第一级台阶： 1种跳法
第二级台阶： 2种跳法
第三级台阶： 3种跳法：要么从第一级跳2级跳上来，要么从第二级跳1级跳上来。
……
第n级台阶：f(n-2)+f(n-1): 要么从n-2级一次跳两级跳上来，那么从n-1级跳一级跳上来。
所以就是一个非常典型的斐波那契数列，最开始两项分别是1和2.

思路1

直接用递归

思路2

用数组保存

思路3

保存两个关键数字

解题代码

思路1代码

class Solution {
public:
    int jumpFloor(int num) {
        //方法1.递归解决
         if(num == 1){
           return 1;
         }else if( num == 2){
            return 2;
         }else{
            return jumpFloor(num-1) + jumpFloor(num-2);
         }
    }
};

思路2代码

class Solution {
public:
    int jumpFloor(int num) {
        // 方法2: 数组保存
         vector<int> a={0,1,2};
         for(int i = 3; i<=num; i++){
             a.push_back(a[i-1]+a[i-2]);
         }
         return a[num];
    }
};

时间复杂度为O(n),空间复杂度为O(n)

思路3代码

class Solution {
public:
    int jumpFloor(int num) {
        // 方法3:
        int first = 1, second = 2;
        if(num == 1) return 1;
        if(num == 2) return 2;
        for(int i = 2; i < num; i++){
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }
};

时间复杂度为O(n),空间复杂度为O(1)
以上，本题结束！