【动态规划篇】面试题 08.01. 三步问题

面试题 08.01. 三步问题

题目链接： 面试题 08.01. 三步问题 题目叙述： 三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。

示例 1：

输入： n= 3 输出： 4 说明： 有四种走法 示例 2：

输入： n = 5 输出： 13 提示:

n范围在[1, 1000000]之间

解题思路：

1. 状态表示 dp[i]表示：到达i位置时一共有多少种方法

1. 状态转移方程 以i位置的状态，最接近的一步来划分问题 第一种情况是从i-1的位置跳一步到达i 第二种情况是从i-2的位置跳两步到达i 第三种情况是从i-3的位置跳三步到达i

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

1. 初始化 保证填表时不越界 若i = 0时会出现负数，同理i=2,3也是 dp[1] = 1,dp[2] = 2,dp[3] = 4
2. 填表顺序 从左往右
3. 返回值 dp[n]

代码实现：

class Solution {
public:
    int waysToStep(int n) {
        //1.创建dp表
        //2.初始化
        //3.填表
        //4.返回值

        const int MOD = 1e9 + 7;

        //处理边界问题
        if (n == 1 || n == 2) return n;
        if (n == 3) return 4;

        vector<int> dp(n + 1);//因为要返回n的值，所以要创建n+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];
    }
};

时间复杂度：O(n) 空间复杂度：O(n)