题解 | #跳台阶#

    public int jumpFloor(int target) {
    //方法一：递归方法
        //跳一次上一级台阶
        //跳两次上2级
        //判定特殊条件,返回的是跳法
//         if(target ==1 ){
//             return 1;
//         }
//         if(target == 2){
//             return 2;
//         }
        
//         return jumpFloor(target -1) + jumpFloor(target -2);
        //方法二： 尝试记忆化搜索
        //寻找重复项，然后用傻缓存
        //1.命名一个傻缓存
        int [] dp = new int[target+1];
        return processus2(target, dp);
    }
    //记忆化搜索，给一个傻缓存，带着进行递归，用于减少重复项，还是需要栈空间
    public static int precessus(int n, int[]dp){
        //1.如果之前算过
        if(dp[n] != 0){
            return dp[n];
        }   
        //2.如果之前没算过
        int ans = 0;
        if(n ==1 ){
            ans = 1;
        }else if(n == 2){
            ans = 2;
        }else{
            ans = precessus(n-1, dp) + precessus(n-2, dp);
        }      
        dp[n] = ans;
        return ans;   
    }
    
    //动态规划，不需要栈空间
    public static int processus2(int n, int []dp){
        
        for(int i = 1; i < n+1; i++){
            if(i == 1){
                dp[1] = 1;
            }else if(i ==2){
                dp[2] = 2;
            }else{
                dp[i] = dp[i-1]+dp[i-2];
            }         
        }
        return dp[n];
    }
}