剑指offer刷题笔记之——变态跳台阶

题目描述

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

问题分析

根据题目描述,我们假设跳n级台阶有f(n)种跳法。每次可以跳1.....n级
(1). 假设一次跳1级,那么剩下n-1级台阶,有f(n-1)种跳法
(2). 假设一次跳2级,那么剩下n-2级台阶,有f(n-2)种跳法
(3). 假设一次跳3级,那么剩下n-3级台阶,有f(n-3)种跳法
....
(n-1). 假设一次跳n-1级,那么剩下1级台阶,有f(1)种跳法
(n-0). 假设一次跳n级,那么剩下0级台阶,有f(0)种跳法

思路

根据分析,我们知道,f(n) = f(n-1) + f(n-2) + ... +f(2) + f(1) + f(0)
而f(n-1) = f(n-2) + f(n-3) + ... +f(2) + f(1) + f(0)
所以f(n) = 2*f(n-1)

              | 1,               (n=0)
     f(n) =   | 1,               (n=1)
              | 2 * f(n-1),      (n>2, n为整数)

代码

C++代码

class Solution {
public:
    int jumpFloorII(int number) {
        if(number <=0)
            return 0;
        if(number == 1)
            return 1;
        else
            return 2 * jumpFloorII(number - 1);
    }
};
发表新评论