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

た入场券 2022-11-26 08:37 98阅读 0赞

## 题目描述 ##

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

## 过程： ##

乍一看毫无思路。

![\\newline f(1)=1 \\newline f(2)=2 \\newline ... \\newline f(n)= f(n-1)+f(n-2)+...+f(1)+1][newline f_1_1 _newline f_2_2 _newline ... _newline f_n_ f_n-1_f_n-2_..._f_1_1]

public class Solution {
        public int JumpFloorII(int target) {
            if(target==1 || target==2) return target;
            int[] list = new int[target];
            list[0]=1;
            list[1]=2;
            for(int i = 2;i<target;i++){
                int num=1;
                for(int j=0;j<i;j++){
                    num = num + list[j];
                }
                list[i]=num;
            }
            return list[target-1];
        }
    }

wuwuwu.写了有一会才AC了，看看题解去。我的时间复杂度为![O(n^2)][O_n_2]，空间复杂度为![O(n)][O_n]。

--------------------

### 继续优化 ###

对于方法一中的：f\[n\] = f\[n-1\] + f\[n-2\] + ... + f\[0\]

那么f\[n-1\] 为多少呢？

f\[n-1\] = f\[n-2\] + f\[n-3\] + ... + f\[0\]

所以一合并，f\[n\] = 2\*f\[n-1\]，初始条件f\[0\] = f\[1\] = 1

所以可以采用递归，记忆化递归，动态规划，递推。具体详细过程，可查看青蛙跳台阶。

这里直接贴出递推的代码。

public class Solution {
        public int JumpFloorII(int target) {
            if(target==1 || target==0) return 1;
            int a = 1, b = 0;
            for (int i=2; i<=target; ++i) {
                b = a << 1; //  口诀：左移乘2，右移除2
                a = b;
            }
            return b;
        }
    }

--------------------

当然，你会发现一个规律：

![\\newline f\[0\] = f\[1\] = 1 \\newline f\[2\] = 2 = 2^1 \\newline f\[3\] = 4 = 2^2 \\newline f\[4\] = 8 = 2^3 \\newline ... \\newline f\[n\] = 2^\{n-1\}][newline f_0_ _ f_1_ _ 1 _newline f_2_ _ 2 _ 2_1 _newline f_3_ _ 4 _ 2_2 _newline f_4_ _ 8 _ 2_3 _newline ... _newline f_n_ _ 2_n-1]

所以，针对本题还可以写出更加简单的代码。

public class Solution {
        public int JumpFloorII(int target) {
            if(target==1 || target==0) return 1;
            return (int) Math.pow(2,(target-1));
        }
    }

[newline f_1_1 _newline f_2_2 _newline ... _newline f_n_ f_n-1_f_n-2_..._f_1_1]: https://private.codecogs.com/gif.latex?%5Cnewline%20f%281%29%3D1%20%5Cnewline%20f%282%29%3D2%20%5Cnewline%20...%20%5Cnewline%20f%28n%29%3D%20f%28n-1%29&plus;f%28n-2%29&plus;...&plus;f%281%29&plus;1
[O_n_2]: https://private.codecogs.com/gif.latex?O%28n%5E2%29
[O_n]: https://private.codecogs.com/gif.latex?O%28n%29
[newline f_0_ _ f_1_ _ 1 _newline f_2_ _ 2 _ 2_1 _newline f_3_ _ 4 _ 2_2 _newline f_4_ _ 8 _ 2_3 _newline ... _newline f_n_ _ 2_n-1]: https://private.codecogs.com/gif.latex?%5Cnewline%20f%5B0%5D%20%3D%20f%5B1%5D%20%3D%201%20%5Cnewline%20f%5B2%5D%20%3D%202%20%3D%202%5E1%20%5Cnewline%20f%5B3%5D%20%3D%204%20%3D%202%5E2%20%5Cnewline%20f%5B4%5D%20%3D%208%20%3D%202%5E3%20%5Cnewline%20...%20%5Cnewline%20f%5Bn%5D%20%3D%202%5E%7Bn-1%7D