动态规划=递归+记忆化存储-跳台阶

在这里插入图片描述

求解代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public int jumpFloor(int number) {
        int[] memo = new int[number + 1];

        return dp(number, memo);
    }

    private int dp(int number,int[] memo){
        if(number<=2){
            return number;
        }
        

        if(memo[number]!=0){
            return memo[number];
        }

        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，就表示已经计算过，直接取值即可。