LCR 127.训练计划 V

难度：🟢 简单

标签：动态规划、记忆化搜索、数学

链接：LCR 127. 跳跃训练 (剑指 Offer 10- II. 青蛙跳台阶问题)

题目描述

一块石子场地有 num 个台阶，第 i 个台阶的高度为 i。一只青蛙要从第 0 个台阶跳到第 num 个台阶，每次它有两种跳跃选择：

• 跳上 1 级台阶

• 跳上 2 级台阶

请问该青蛙跳上一个 num 级的台阶总共有多少种跳法？

答案需要取模 1000000007（1e9+7），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：num = 2
输出：2

示例 2：

输入：num = 7
输出：21

示例 3：

输入：num = 0
输出：1

解题思路

核心思想

本题是动态规划的经典入门问题，其本质是求解一个斐波那契数列。要跳到第 n 级台阶，只能从第 n-1 级或第 n-2 级跳上来。因此，跳到第 n 级的方法数 f(n) 等于跳到第 n-1 级的方法数 f(n-1) 与跳到第 n-2 级的方法数 f(n-2) 之和。

• f(0) = 1 (一种方法：不跳)

• f(1) = 1

• f(2) = 2

• 状态转移方程： f(n) = f(n-1) + f(n-2)

思路选择

动态规划（空间优化） 是解决此问题的最优思路。

• 由于计算 f(n) 只需要前两个状态 f(n-1) 和 f(n-2)，我们无需创建一个完整的 dp 数组。

• 只需用两个变量来滚动记录前两个状态的值即可，从而将空间复杂度从 O(n) 优化到 O(1)。

关键步骤

1. 处理边界情况：处理 num = 0 和 num = 1 的情况。

2. 初始化：初始化两个变量 first = 1 和 second = 1，分别代表 f(0) 和 f(1) 的结果。

3. 循环迭代：从 i = 2 开始循环到 num。 a. 在循环中，计算当前的方法数 temp = (first + second) % 1000000007。 b. 更新状态：将 first 更新为原来的 second，将 second 更新为 temp，为计算下一阶做准备。这个过程被称为“滚动数组”。

4. 返回结果：循环结束后，second 变量中存储的就是最终结果。

代码实现

/**
 * @param {number} num
 * @return {number}
 */
var trainWays = function (num) {
    // 处理 n=0 和 n=1 的基本情况
    if (num === 0) return 1;
    if (num <= 2) return num;

    // 初始化 f(1) 和 f(2)
    let first = 1, second = 2;
    const MOD = 1000000007;

    for (let i = 3; i <= num; i++) {
        // 计算 f(i) 并取模
        let temp = (first + second) % MOD;
        // 滚动更新
        first = second;
        second = temp;
    }

    return second;
};

复杂度分析

• 时间复杂度：O(n) 我们只需要一个从 3 到 n 的循环，循环次数与 n 成正比。

• 空间复杂度：O(1) 我们只使用了常数个额外变量，与输入 num 的大小无关。

相关题目

• 0070.爬楼梯

• 0509.斐波那契数

• 0198.打家劫舍

总结

本题是斐波那契数列的变种，是动态规划的经典入门题。其解法的核心是识别出状态转移方程，并使用滚动数组的思想进行空间优化，从而得到一个既高效又节省空间的解决方案。