题解 | 跳台阶

import java.util.*;


public class Solution {
/**
     * 跳台阶问题的公共接口方法
     *
     * @param number 台阶总数
     * @return 返回跳上number级台阶的总方法数
     */
    public int jumpFloor(int number) {
        // 创建备忘录数组，用于存储已经计算过的结果
        int[] memo = new int[number + 1];

        // 调用动态规划方法计算结果
        return dp(number, memo);
    }

    /**
     * 动态规划方法，使用备忘录优化递归
     *
     * @param number 当前要计算的台阶数
     * @param memo   备忘录数组，存储已经计算过的结果
     * @return 返回跳上number级台阶的方法数
     */
    private int dp(int number, int[] memo) {
        // 基本情况：当台阶数小于等于2时，直接返回台阶数
        if (number <= 2) {
            return number;
        }


        // 如果备忘录中已经存在该结果，直接返回备忘录中的值，避免重复计算
        if (memo[number] != 0) {
            return memo[number];
        }

        // 使用递推关系：f(n) = f(n-1) + f(n-2)
        // 将计算结果存入备忘录并返回
        memo[number] = dp(number - 1, memo) + dp(number - 2, memo);

        return memo[number];
    }
}