题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：其实和跳台阶思路很像，
（1）跳一级台阶 ：
1 一种
（2）跳二级台阶 ：
11/2 两种
（3）跳三级台阶 ：
先跳一级还有两级台阶同情况（2） 记作=> 1 （2）
先跳两级还有一级台阶同情况（1） 记作=> 2 （1）
先跳三级台阶情况 记作=> 3
把这三种情况加起来就是跳三级台阶的一共可能
（2）+（1）+1
（4）跳四级台阶 ：
先跳一级还有三级台阶同情况（3） 记作=> 1 （3）
先跳两级还有两级台阶同情况（2） 记作=> 2 （2）
先跳三级还有一级台阶同情况（1） 记作=> 3 （1）
先跳四级台阶情况 记作=> 4
把这两种情况加起来就是跳四级台阶的一共可能
（4）+（3）+（2）+（1）+1
（5）跳五级台阶 ：
先跳一级还有四级台阶同情况（4） 记作=> 1 （4）
先跳两级还有三级台阶同情况（3） 记作=> 2 （3）
先跳三级还有二级台阶同情况（2） 记作=> 3 （2）
先跳四级还有一级台阶同情况（1） 记作=> 4 （1）
把这两种情况加起来就是跳五级台阶的一共可能
（5）+（4）+（3）+（2）+（1）+1
...
以此类推
我的思路实现：
function jump(n){
if(n<=2){
return n;
}
if(n>2){
var arr = [1,2];
for(var i=3;i<=n;i++){
var res=0;
for(var j=0;j<arr.length;j++){
res += arr[j]
}
arr.push(res+1)
}
return arr[n-1]
}
}
然而看了大牛的代码：
function jumpFloorII(number)
{
return 1<<(--number);
}
你就说你服不服吧
<< :
比如 var temp=14<<2
那么temp为56
因为：
变量14的二进制表示为00001110，按位左移2位后二进制为00111000，转为十进制为56
那么temp为56
因为：
变量14的二进制表示为00001110，按位左移2位后二进制为00111000，转为十进制为56
其实推到推到会发现规律的，2的幂次方相关,于是就有了
function jumpFloorII(number)
{
return Math.pow(2,number-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)
实现：
function jumpFloorII(number)
{
if(number==1||number==2){
return number
}
return 2*jumpFloorII(number-1)
}