剑指offer-变态跳台阶

本文为剑指 offer 系列第十一篇。
主要知识点为找规律，可以作为上一篇跳台阶的升级版,依旧比较简单。

题目描述

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

解题思路

直接找规律。

1. 第一级台阶：1种方式。
2. 第二级台阶：2种方式。1+1 ：直接跳到2级或者从1级上跳上来。
3. 第三级台阶：4种方式。1+1+2 ：直接跳到3级或者从1级跳上来或者从2级跳上来。
4. ……
5. 第n级台阶：2^(n-1)种方式。 1+1+2+4+……+2^(n-2) = 2^(n-1)。直接跳到n级或者从前面的每一级跳到当前n级。

解题代码

class Solution {
public:
    int jumpFloorII(int number) {
        return pow(2,number-1);
    }
};

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

以上，本题结束！