题解 | #跳台阶#

先模拟了1、2、3、4、5个台阶能有多少种跳法，找规律，f(n)=f(n-1)+f(n-2)

首先是递归，递归最重要的是找到出口，即跳出递归的条件，那就是一个台阶的时候只有1种跳法

public class Solution {
    public int jumpFloor(int target) {
         if(target<=1)return 1;
         return jumpFloor(target-1)+jumpFloor(target-2);
    }
}

递归是往下找到出口，再往上收拢，而且有重复计算的地方，这部分时间可以省略，那就将值用数组或map存下来

public class Solution {
    static int[] f = new int[50];
    public int jumpFloor(int target) {
         if(target<=1)return 1;
         if(f[target]>0)return f[target];
         return f[target] = jumpFloor(target-1)+jumpFloor(target-2);
    }
}

不考虑递归，直接循环也挺好的，值存入数组中

public class Solution {
    static int[] f = new int[50];
    public int jumpFloor(int target) {
    	f[0]=1;
        f[1]=1;
        for(int i=2;i<=target;i++)f[i]=f[i-1]+f[i-2];
        return f[target];
    }
}

宇宙的尽头是数学吧。。 只用2个变量存储

public class Solution {
    static int[] f = new int[50];
    public int jumpFloor(int target) {
        int a=1,b=1,c=1;
        for(int i=2;i<=target;i++){
            c=a+b;a=b;b=c;
        }
        return c;
    }
}