剑指Offer——II. 青蛙跳台阶问题（JS实现）

题目描述

解题思路一（暴力法）

1. 当只有一级台阶的时候 F(1) = 1  只有一种跳法
2. 当有两级台阶的时候 要么 1 + 1  要么 2  所以，F(2) = 2,此时有两种跳法
3. 当台阶数大于2的时候，我们只用考虑最后一步的跳法
4. 最后一步要么跳1步，要么跳2步
5. 假设最后一步跳的是1步，则F(n) = F(n-1) + 1;
6. 假设最后一步跳的是2步，则F(n) = F(n-2) + 1;
7. 所以最后一步有这样的跳法 F(n) = F(n-1) + F(n-2);
8. 最后得到的答案要取模 % 1000000007

解题代码一（超时，时间复杂度太高）

var numWays = function(n) {
    // 当只有一级台阶的时候 F(1) = 1  只有一种跳法
    // 当有两级台阶的时候 要么 1 + 1  要么 2  所以，F(2) = 2,此时有两种跳法
    // 当台阶数大于2的时候，我们只用考虑最后一步的跳法
    // 最后一步要么跳1步，要么跳2步
    // 假设最后一步跳的是1步，则F(n) = F(n-1) + 1;
    // 假设最后一步跳的是2步，则F(n) = F(n-2) + 1;
    // 所以最后一步有这样的跳法 F(n) = F(n-1) + F(n-2);
    // 最后得到的答案要取模 % 1000000007
    if (n === 1) return 1;
    if (n === 2) return 2;
    if (n === 0) return 1;
    return (numWays(n-1) + numWays(n-2)) % 1000000007
};

解题思路二（备忘录的方法）

上面的解法之所以会超时，原因在于上面存在两个递归，第二个递归和第一个递归走了重复的路，因此时间复杂度较高，下面我们采用备忘录的方法，所谓的备忘录的方法就是用一个数组将第一个递归走过的路记录下来，这样第二的递归可以直接用，这样时间复杂度就会降下来。

解题代码二

var numWays = function(n) {
    // ! 备忘录的方法
    // 定义一个备忘录
    // 这里之所以要n+1，就是要确保数组的最后一个元素的下标就是台阶数
    // 这里之所以填充负数，原因在于走法不可能是负数，用此来判断这个位置是否被遍历过
    const cache = new Array(n + 1).fill(-1);
    dfs(n,cache);
    return cache[n];
};
function dfs(n,cache) {
    // 下面的两个条件是递归的基础条件
    if (n <= 1) cache[n] = 1;
    if (n === 2) cache[n] = 2;
    // 下面的这个是用来判断该位置是否已经填充，如果已经填充则不需要继续了，直接返回即可
    if (cache[n] !== -1) return cache[n];
    cache[n] = (dfs(n - 1,cache) + dfs(n - 2,cache)) % 1000000007;
    return cache[n];
}

总结（本题给我们的启示思路）

• 启示：学会使用备忘录数组的方法来记录已经递归过的元素，降低递归的时间复杂度。