【剑指Offer】变态跳台阶（推导）

59 阅读 0 评论 39 点赞

我是靠谱客的博主负责大白，最近开发中收集的这篇文章主要介绍【剑指Offer】变态跳台阶（推导），觉得挺不错的，现在分享给大家，希望可以做个参考。

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

思路：写过，答案就出来了。1<<(n-1)

写一下分析。

青蛙一次可以跳上1，2，……，n级。

f(1)=1;

f(2)=f(2-1)+f(2-2);//对于二级台阶，f(2-1)为一次跳1级的次数；f(2-2)为一次跳2级的次数后面类似

f(3)=f(3-1)+f(3-2)+f(3-3);

……

f(n-1)=f((n-1)-1)+f((n-1)-2)+……+f((n-1)-n-1);

f(n)=f(n-1)+f(n-2)+……+f(n-(n-1))+f(n-n);

合并最后两个等式得：

f(n)=f(n-1)+f(n-1)=2*f(n-1)，n>1

f(n)=1，n=1 （可得f(0)=1）

综上可得，f(n)=2^(n-1) ，n>=1

代码：

class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<(number-1);
    }
};

以上就是负责大白为你收集整理的【剑指Offer】变态跳台阶（推导）的全部内容，希望文章能够帮你解决【剑指Offer】变态跳台阶（推导）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。