【剑指offer】变态跳台阶

题目描述

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

解决方案

思路：接上一个跳台阶问题思路继续分析，上个问题中，青蛙只能跳1级或者2级。 则最后一跳只有两种可能，所以F(n) = F(n-1) + F(n-2)//现在青蛙可以跳n级。 假设台阶为n级，则青蛙可以 跳一次或者多次。 一次： 直接跳n级，这是一种方法。 多次： 青蛙跳到 1到n-1级 任一级（不管怎样跳，跳几次）后再跳一次到n级。//或者这样分析，青蛙最后一跳，有可能是从起点直接跳到终点，或者从起点跳了若干步后(到达 1到n-1级中间任一级 )再跳到n级。//所以总的方法数为：青蛙 跳到 1级到n-1级 每级可能的方法数（再跳到n级） + 1（直接跳到n级）

f(n) = f(n-1)+f(n-2) + … +f(1)
f(n-1) = f(n-2)+f(n-3)+ … f(1)
综上：
f(n) = 2*f(n-1)

class Solution {
public:
    int jumpFloorII(int number) {
        if (number < 1)
        {
            return 0;
        }
        if (number == 1)
        {
            return 1;
        }
	return 2 * jumpFloorII(number - 1);
    }
};