滚动数组-动态规划（跳跃训练-费波那契数列）

半夏の微凉

已于 2024-10-21 16:57:27 修改

阅读量1.1k

点赞数 21

文章标签：算法 leetcode 职场和发展

于 2024-10-21 16:33:54 首次发布

本文链接：https://blog.csdn.net/csdnuu123/article/details/143115665

版权

跳跃训练：

今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 num 个小格子，每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中，学员们共有多少种不同的跳跃方式。

结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 5
输出：8

提示：

0 <= n <= 100

我的解法：动态规划

这个问题和典型的“爬楼梯”问题非常相似。每次可以选择跳一个格子或两个格子，因此，求解的方式可以通过动态规划来解决。

假设：

dp[i] 表示跳到第 i 个格子的不同跳跃方式数。
如果我们站在第 i 个格子，可以从第 i-1 个格子跳一步到达，或者从第 i-2 个格子跳两步到达。因此，状态转移方程为：
dp[i]=dp[i−1]+dp[i−2]
其中 dp[1] = 1（只有一种方式跳到第一个格子），dp[2] = 2（跳到第二个格子可以选择跳一步+一步，或者直接跳两步）。

为了避免结果过大，题目要求我们在每次计算时对结果取模 1e9+7。

class Solution {
    public int trainWays(int num) {
        int MOD = 1000000007; // 定义取模数
        if(num==0){
            return 1;
        }
        
        if (num == 1) {
            return 1;
        }
        if (num == 2) {
            return 2;
        }
        
        int[] dp = new int[num]; // 动态规划数组
        dp[0] = 1;
        dp[1] = 2;
        
        for (int i = 2; i < num; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; // 每次计算都要取模
        }
        
        return dp[num - 1]; // 返回最终结果
    }
}

滚动数组解法：

class Solution {
    public int trainWays(int num) {
        int MOD = 1000000007;
        
        // 基本情况
        if (num == 1) {
            return 1;
        }
        if (num == 2) {
            return 2;
        }
        
        // 动态规划初始状态
        int prev2 = 1;  // 相当于 dp[1]
        int prev1 = 2;  // 相当于 dp[2]
        
        // 从第3个格子开始递推
        for (int i = 3; i <= num; i++) {
            int current = (prev1 + prev2) % MOD;  // dp[i] = dp[i-1] + dp[i-2]，取模
            prev2 = prev1;  // 更新 prev2
            prev1 = current;  // 更新 prev1
        }
        
        // 返回 dp[num]，即 prev1 的值
        return prev1;
    }
}

滚动数组解法和动态规划解法的核心思想相同，都是通过记录子问题的解来求解更大规模的问题。它们之间的主要区别在于 空间优化。让我们详细讨论它们的区别和滚动数组解法的局限性。

1. 动态规划解法

动态规划通常通过构建一个数组 dp[] 来存储中间状态。每个 dp[i] 代表到达第 i 个状态的解法数，最终我们通过递推得到 dp[num] 的解。

优点：

逻辑简单，易于理解和实现。
可以轻松处理复杂的问题状态和多维状态。

缺点：

空间复杂度高：通常会使用一个大小为 n 的数组来存储中间结果（比如跳格子问题中的 dp[num]），即使有些中间状态在后续计算中不再需要，仍然会占用内存。

2. 滚动数组解法

滚动数组解法是动态规划的一种 空间优化 技巧。它的基本思想是，由于状态转移方程通常只依赖于前几项（例如斐波那契数列只依赖于前两项），所以我们不需要维护整个数组，只需要记录当前状态和前一个（或前两个）状态即可。

滚动数组解法的步骤：

当问题的状态转移方程简单且依赖的状态较少时，滚动数组解法非常适合。然而，对于依赖更多前置状态或复杂多维问题，滚动数组解法的应用局限性会显现出来。

只保存几个必要的状态变量，省去不再使用的状态。
比如在跳格子问题中，状态转移方程 dp[i] = dp[i-1] + dp[i-2] 只依赖于 dp[i-1] 和 dp[i-2]，所以我们只需要保存这两个值。

优点：

空间复杂度低：滚动数组解法将空间复杂度从 O(n) 降低为 O(1)，因为只存储了固定数量的状态，而不是所有的中间结果。

缺点（局限性）：

只适用于状态转移依赖较少的情况：
滚动数组只能优化那些状态转移方程依赖较少前置项的问题（如仅依赖 dp[i-1] 和 dp[i-2]）。
如果问题的状态转移方程依赖于多个前置状态（如 dp[i] 可能依赖 dp[i-1], dp[i-2], dp[i-3] 等等），滚动数组的空间优化效果就会变差。
不适用于复杂的多维动态规划问题：
如果是二维或多维动态规划问题（比如矩阵路径问题等），很难通过滚动数组来实现空间优化。因为每个状态的依赖项不仅限于前一行或者前一列，还可能是多个其他维度的数据，这种情况下，通常需要完整地保留整个状态数组。
可读性稍差：
对于某些较为复杂的问题，滚动数组解法由于不断更新有限的几个状态变量，可能会使代码的可读性下降，因为我们需要时刻追踪变量之间的更新关系，而不像动态规划解法那样直观地维护一个数组。

总结

解法	空间复杂度	适用场景	优点	缺点
动态规划（DP）	O(n)	大多数动态规划问题	逻辑清晰，易于理解，适用于多维问题	空间复杂度高
滚动数组（空间优化）	O(1)	状态转移依赖少的动态规划问题（如斐波那契数列）	空间复杂度低，节省内存	只适用于状态依赖较少的情况，不适用复杂的多维问题