题解 | #跳台阶#

非递归

使用dp[]数组进行存储

public class Solution {
    public int jumpFloor(int target) {
        int[] dp = new int[41];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<target+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[target];
    }
}

优化：每次只用到i-1、i-2两个值，因此可以优化存储空间

public class Solution {
    public int jumpFloor(int target) {
        if(target==1)return 1;
        if(target==2)return 2;
        int a=1;
        int b=2;
        int dp_i=0;
        for(int i=3;i<target+1;i++){
            dp_i=a+b;
            a=b;
            b=dp_i;
        }
        return dp_i;
    }
}