【剑指offer】09 变态跳台阶

题目描述

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

时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 64M，其他语言128M

题目示例

输入：

返回值：

解法分析

跳台阶进阶版，与跳台阶类似，当有n节台阶时，如果青蛙最后一步跳一节，那么它跳n-1节台阶时有多少种跳法，跳n节台阶时就有多少种跳法；如果青蛙最后一步跳两节，那么它跳n-2节台阶时有多少种跳法，跳n节台阶时就有多少种跳法……如果青蛙最后一步跳n节，那么它跳0节台阶时有多少种跳法，跳n节台阶时就有多少种跳法。可以看出，跳n节台阶的跳法种类，相当于跳n-1节台阶和跳n-2节台阶和……和跳0节台阶跳法的和。

即f[n]=f[n-1]+f[n-2]+...+f[0]，代码可见算法1。

然而我们可以看出，f[n-1]=f[n-2]+f[n-3]+...+f[0]，f[n]-f[n-1]=f[n-1]，即f[n]=2*f[n-1]，这样我们就可以得到更简便的算法，详见算法2。

代码

算法1：

 1 function jumpFloorII(number)
 2 {
 3     // write code here
 4     if(number<=1){
 5         return 1;
 6     }else{
 7         var fib = new Array();
 8         fib[0] = 1;
 9         fib[1] = 1;
10         for(var len=2;len<=number;len++){
11             fib[len] = 0;
12         }
13         for(var i=2;i<=number;i++){
14             for(var j=0;j<i;j++){
15                 fib[i]+=fib[j];
16             }
17         }
18         return fib[number];
19     }
20 }

算法2：

1 function jumpFloorII(number)
2 {
3     // write code here
4     var res = 1;
5     while(--number){
6         res*=2;
7     }
8     return res;
9 }

执行结果