【牛客】9、青蛙变态跳台阶（斐波那契数列）

62 阅读 0 评论 41 点赞

我是靠谱客的博主大力饼干，最近开发中收集的这篇文章主要介绍【牛客】9、青蛙变态跳台阶（斐波那契数列），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

思路：
当n=1时，f(1)=1
当n=2时，f(2)=2
当n=3时，第一步可以跳一阶，剩下的是f(2)；或者第一步可以跳两节，剩下的是f(1)。即f(3)=f(2)+f(1)
…
当n阶台阶，第一步可以跳一阶，剩下的是f(n-1)；或者第一步可以跳两节，剩下的是f(n-2)；第一步可以跳3阶…
f(n)=f(n-1)+f(n-2)+f(n-3)+…+f(2)+f(1).
类似的f(n-1)=f(n-2)+f(n-3)+…+f(2)+f(1)，那么f(n)=2*f(n-1).

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