本文共 2218 字，大约阅读时间需要 7 分钟。

青蛙跳台阶问题是一个经典的动态规划题目，要求计算一只青蛙跳上n级台阶的总方法数。青蛙每次可以跳1步或2步。以下是基于动态规划的不同方法及其优化的详细解析。

题目描述

一只青蛙可以跳1步或2步台阶。求青蛙跳上n级台阶的总方法数。答案需要取模1000000007。

动态规划方法

方法一：备忘录（记忆化递归）

备忘录法是一种自顶而下的方法。每次遇到需要解决的问题时，先检查是否有缓存结果，如果有则直接使用；如果没有，则先解决这个问题，记录结果供以后使用。

代码示例：

numWays = function(n) {
    let cache = new Array(n + 1).fill(-1);
    getCount(n, cache);
    return cache[n];
}
function getCount(n, cache) {
    if (n <= 1) {
        cache[n] = 1;
    } else if (n === 2) {
        cache[n] = 2;
    }
    if (cache[n] !== -1) {
        return cache[n];
    } else {
        cache[n] = (getCount(n - 1, cache) + getCount(n - 2, cache)) % 1000000007;
        return cache[n];
    }
}
// 测试
console.log(numWays(1));
console.log(numWays(2));
console.log(numWays(10));
console.log(numWays(0));

优点： 需要函数内部缓存，适合递归实现较为自然。

缺点： 由于步数递归频繁调用，存在较大的函数调用的开销，尤其对于较大的n值，性能可能不佳。

方法二：自底向上（迭代法）

自底向上方法从处理更小的问题开始，一步步建往前，避免了函数调用带来的开销，提高了性能和效率。

代码示例：

numWays2 = function(n) {
    let cache = new Array(n + 1).fill(-1);
    cache[0] = 1;   // 到达0阶的方法数有1种（不动）
    cache[1] = 1;   // 到达1阶只能跳1步，有1种方法
    if (n === 2) {
        cache[2] = 2;  // 跳1跳2各一
    } else {
        for (let i = 3; i <= n; i++) {
            cache[i] = (cache[i-1] + cache[i-2]) % 1000000007;
        }
    }
    return cache[n];
}
// 测试
console.log(numWays2(1));
console.log(numWays2(2));
console.log(numWays2(10));
console.log(numWays2(0));

优点： 时间复杂度O(n)，空间复杂度O(n)，步骤清晰，容易理解和实现。

缺点： 所需数组空间与n成正比，较大的n造成较大空间消耗。

方法三：临时数保存

由于青蛙跳台阶数n只与n-1和n-2有关，可以在迭代过程中仅保存前两个值而不使用数组，节省空间。

代码示例：

numWays3 = function(n) {
    if (n === 1 || n === 0) {
        return 1;
    }
    if (n === 2) {
        return 2;
    }
    let val1 = 1; // 表示n-1的跳法，对应跳1步的情况
    let val2 = 2; // 表示n-2的跳法，对应跳2步的情况
    let result = val1 + val2;
    for (let i = 3; i <= n; i++) {
        result = (val1 + val2) % 1000000007;
        val1 = val2;
        val2 = result;
    }
    return result;
}
// 测试
console.log(numWays3(1));
console.log(numWays3(2));
console.log(numWays3(10));
console.log(numWays3(0));

优点： 时间复杂度O(n)，空间复杂度O(1)，最节省空间。

缺点： 变量依赖较强，需要维护状态变量，代码稍显复杂。

总结

上述三种方法各有适用场景：

• 备忘录法：代码实现简单，适合递归思考者，使用前提。
• 自底向上迭代法：时间和空间都较为优化，推荐使用。
• 临时数保存法：在空间效率上最优，适合不需要同时存储所有中间结果的场景。

选择哪种方法主要看具体问题需求，如n的范围和所需性能。对于大部分动态规划问题，自底向上的迭代方法是一种较为平衡的选择，兼顾了时间和空间复杂度。