题目描述

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

题解

分析

把跳 n 级台阶定义为 f(n)，
先试着从基础样本找规律：

  1. f(1) = 1，一步走完
  2. f(2) = f(1) + 1 = 2，两种情况，一种是直接走 1 个两步，一种是走 2 个一步
  3. f(3) = f(1) + f(2) + 1 = 4，四种情况，一种是走 3 个一步，两种是走 1 个一步后，剩下两步即 f (2)，一种是走 1 个两步后，剩下一步即 f(1)
  4. f(4) = f(1) + f(2) + f(3) + 1 = 8，同理
  5. …
  6. f(n-1) = f(1) + f(2) + f(3) + … + f(n-2)
  7. f(n) = f(1) + f(2) + f(3) + … + f(n-1)

即 f (n) = 2f(n-1)
得出规律：台阶数与跳法数是一个初项为 1，等比为 2 的等比数列

代码

class Solution {
public:
    int jumpFloorII(int number) {
        if(number == 1)
             return 1;
        return 2 * jumpFloorII(number-1);
        // 或者直接自己算
        // return pow(2,number-1);
    }
};