C++ 动态规划：第 N 个泰波那契数与三步问题

空间优化根据滚动数组来进行模拟优化

02. 三步问题

题目链接：

面试题 08.01. 三步问题 - 力扣（LeetCode）

题目描述：

题目示例：

算法原理（动态规划）：

思路：

1. 状态表示： 这道题可以根据经验加题目要求直接定义出状态表示：

dp[i] 表示：到达 i 位置时，一共有多少种方法。

2. 状态转移方程： 以 i 位置状态的最近的一步，来分情况讨论： 如果 dp[i] 表示小孩上第 i 阶楼梯的所有方式，那么他应等于所有上一步的方式之和：

• 上一步上一级台阶：dp[i] += dp[i-1]
• 上一步上两级台阶：dp[i] += dp[i-2]
• 上一步上三级台阶：dp[i] += dp[i-3]

综上所述，dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

需要注意的是，这道题目说，由于结果可能很大，需要对结果取模。

在计算的时候，三个值全部加起来再取模是不行的。对于这类问题，我们每计算一次（两个数相加），都需要取一次模。否则，万一发生了溢出，我们的答案就错了。

3. 初始化 从递推公式可以看出，dp[i] 在 i=0, i=1 以及 i=2 的时候没有办法进行推导，因为 dp[-3], dp[-2] 或 dp[-1] 不是一个有效的数据。

因此我们需要在填表之前，将 1, 2, 3 位置的值初始化。 根据题意，dp[1] = 1, dp[2] = 2, dp[3] = 4。

4. 填表顺序 毫无疑问是【从左往右】。

5. 返回值 应该返回 dp[n] 的值。

解法代码（C++）：

class Solution {
    const int MOD = 1e9 + 7;
public:
    int waysToStep(int n) {
        // 处理边界情况
        if (n == 1 || n == 2) return n;
        if (n == 3) return 4;

        // 空间优化：使用滚动数组模拟
        int a = 1, b = 2, c = 4, d = 0;
        for (int i = 4; i <= n; i++) {
            d = ((a + b) % MOD + c) % MOD;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }
};