每日一练：【动态规划算法】斐波那契数列模型之三步问题（easy）

1. 题目链接：面试题 08.01. 三步问题

2.题目描述

这道题目就是一道的典型的跳台阶问题，小孩从地面往上跳，一次可以跳一层台阶，跳两层台阶，三层台阶，现在我们要求跳到n阶有多少种跳法，结果可能很大，需要取模1e9+7.

3. 解法（动态规划）

1. 状态表示

我们根据 题目要求，我们以第i位置为结尾，我们、、我们定义dp第i个位置存储的值含义是到达 i 位置时，一共有多少种方法。

2. 状态转移方程

我们以 i 位置状态来划分整道题目，我们来考虑距离i位置最近的一步，分情况讨论： 如果如果小孩想要跳到第i层台阶，那么因为小孩一次只能跳1或2或3层台阶，那么小孩要想到达第i层台阶，最少小孩在i- 1层台阶，他就可以直接到达i，或者小孩在i-2,他也可以直接跳到i，或者小孩在i-3他也是可以直接到达i（其他如从i-3跳到i-2再跳到i-1再跳到i，本质上是小孩再到i-1再直接跳到i）。

我们把所有情况归纳为直接到达i的三种情况，那么我们求由于从i-1直接一步跳到i时，求到达的方式就是到达i-1的方式，由于从i-2直接一步跳到i时，求到达的方式就是到达i-2的方式，由于从i-3直接一步跳到i时，求到达的方式就是到达i-3的方式，依次类推。

dp[i] 表示小孩上第 i 阶楼梯的所有方式，那么步的方式之它应该等于所有上一和： i. 上一步上一级台阶， dp[i] += dp[i - 1] ； ii. 上一步上两级台阶， dp[i] += dp[i - 2] ； iii. 上一步上三级台阶， dp[i] += dp[i - 3] ； 综上所述， dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 。 需要注意的是，这道题目说，由于结果可能很大，需要对结果取模。 在计算的时候，三个值全部加起来再取模，即 (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD 是不可取的，大家可以试验一下， n 取题目范围内最大值时，网站会报错 signed integer overflow 。对于这类需要取模的问题，我们每计算一次（两个数相加/乘等），都需要取一次模。否则，万一发生了溢出，我们的答案就错了。

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] 的值。

4.算法代码

class Solution {
public:
    int waysToStep(int n) {
        if(n == 1|| n == 2) return n;
        if(n == 3) return 4;

        vector<int> dp(n + 1);

        const int MOD = 1e9 + 7;

        dp[0] = 1,dp[1] = 1,dp[2] = 2,dp[3] = 4;

        for(int i = 4;i <= n;i++)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }

        return dp[n];
    }
};