[LeetCode] 面试题08.01 三步问题

题目描述：

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

示例1:

 输入：n = 3 
 输出：4
 说明: 有四种走法

示例2:

 输入：n = 5
 输出：13

提示:

1. n范围在[1, 1000000]之间

题目链接：

. - 力扣（LeetCode）

解题主要思路：

其实这题跟 "第N个泰波那契数" 是一类型的，动态规划即可。

• 首先我们先理清dp[i]表示什么？dp[i]表示到达i位置时，一共有多少方式。
• 其次我们需要理清状态转移方程，dp[i]表示dp[i]表示到达i位置时一共有多少方式，且小孩一次可以上1阶、2阶或3阶，那么我们可以理解为：

                小孩从dp[i-3]一次上3阶;

                小孩从dp[i-2]一次上2阶;

                小孩从dp[i-1]一次上1阶；

        因此状态转移方程可以表示为dp[i] = dp[i-3] + dp[i-2] + dp[i-1];不过题目说了结果可能很大，            需要对结果模1000000007，所以我们每相加一次就需要对数据取模。

• 然后我们需要注意dp表的初始化以及边界问题，例如当i = 1时，dp[i-3]就越界了，因此当i [1,3]时我们需要单独拿出来判断。
• 最后我们要注意dp表填表顺序以及返回值即可。

解题代码：

class Solution {
public:
    const int MOD = 1e9+7;  // 1000000007
    int waysToStep(int n) {
        // 边界情况
        if (n == 1 || n == 2) return n;
        if (n == 3) return 4;
        vector<int> dp(n+1);  // 创建dp表
        dp[1] = 1, dp[2] = 2, dp[3] = 4;  // 初始化
        for (int i = 4; i <= n; ++i)
        {   // 构建dp表
            dp[i] = ((dp[i-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;
        }
        return dp[n];
    }
};