题解 | #跳台阶#

import java.util.*;
/**
方法1：暴力递归，时间复杂度超过了，是n的指数O(2^n)
方法2：用空间换时间，把部分重复计算的保存起来，遇到后就直接返回。
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型
     * @return int整型
     */
    //全局
    int[] dp = new int[1024];
    public int jumpFloor (int number) {
        return DF(number);
    }

    public int DF(int number) {
        if (number <= 1) {
            return 1;
        }

        if(dp[number] !=0){
            //有值不用计算直接返回
            return dp[number];
        }

        //把计算的结果存起来放到申明的数组中
        // 后面的递归进来后如果没有值再计算
        dp[number] =  DF(number - 1) + DF(number - 2);
        return dp[number];
    }
}