NO9、变态跳台阶

本文主要是介绍NO9、变态跳台阶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

9、变态跳台阶过，豁然开朗
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

示例1
输入

1|3

返回值

1|4
1、看了讲解豁然开朗

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以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)int jumpFloorII(int number) {if(number==1) return 1;return 2*jumpFloorII(number-1);}`

2、第二种方法

int jumpFloorII(int number) {if(number==1) return 1;int count=0,a=1;for(int i=2;i<=number;++i){count=a*2;a=count;}return count;
}

二刷：还行，找好规律

运行时间：4ms 占用内存：488k

  int jumpFloorII(int number) {if( number <= 1) return number;return pow(2, number-1);
}

美女帅哥们如果觉得写的还行，有点用的话麻烦点个赞或者留个言支持一下阿秀~
如果觉得狗屁不通，直接留言开喷就完事了。

需要该笔记PDF版本的去个人公众号【拓跋阿秀】下回复“阿秀剑指offer笔记”即可。

这篇关于NO9、变态跳台阶的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---