思路

求解代码

/**
     * 跳台阶问题的公共接口方法
     *
     * @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];
    }

小贴士

1.要跳到第 n 级，最后一步只有两种可能：从 n-1 级跳 1 级上来、从 n-2 级跳 2 级上来，总方法数就是两者之和。

2.构建一个备忘录数组，用来缓存已经计算过的结果，数组下标对应台阶数，值对应该台阶的跳法数。

由于数组的默认值为0，0就表示该台阶的跳法数还未计算；

如果值≠0，就表示已经计算过，直接取值即可。