LCR-127 跳跃训练

一个经典的动态规划问题，类似于爬楼梯问题。学员们可以选择每次跳一个格子或两个格子，问在 num 个小格子的平台上共有多少种不同的跳跃方式。这个问题可以用动态规划的方法来解决。

我们定义 dp[i] 为跳到第 i 个格子的不同跳跃方式的数量。根据题意，可以得到状态转移方程：

dp[i] = dp[i-1] + dp[i-2]

即跳到第 i 个格子的方法可以由以下两种情况组成：

1. 从第 i-1 个格子跳一步到达。
2. 从第 i-2 个格子跳两步到达。

边界条件是：

• 当 i == 0 时，dp[0] = 1，表示从起点（第0个格子）到达起点的方式有1种（即不动）。
• 当 i == 1 时，dp[1] = 1，表示从起点跳一步到第一个格子的方式有1种。

最后需要注意的是，结果需要取模 (10^9 + 7)，以防止结果过大。

下面是实现这个算法的代码：

class Solution {
    public int trainWays(int num) {
        // 定义取模常数
        final int MOD = 1000000007;

        // 特殊情况处理
        if (num == 0) return 1;
        if (num == 1) return 1;

        // 初始化dp数组
        int[] dp = new int[num + 1];
        dp[0] = 1;
        dp[1] = 1;

        // 计算每一个dp值
        for (int i = 2; i <= num; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        return dp[num];
    }
}

代码解释

1. 定义 MOD 为 (10^9 + 7) 以确保结果不超过这个范围。
2. 处理特殊情况，当 num 为 0 或 1 时，直接返回 1。
3. 初始化 dp 数组，其中 dp[0] 和 dp[1] 都为 1。
4. 使用循环计算 dp[i]，从 dp[2] 到 dp[num]。
5. 最终返回 dp[num]。

这个方法时间复杂度为 (O(n))，空间复杂度也是 (O(n))。考虑到 num 的最大值为 100，这个方法是高效且可行的。