三步问题

题目：

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

示例：

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

说明：

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

解题方法：

这道题也是一道非常简单的动规题。除了需要计算实现方案数量，还要对结果取模，取模可以防止数值溢出。如果直接对最终计算结果取模可能在计算过程中会放生溢出，所以，需要在计算过程中就取模，利用的公式就是：

(a+b)%c=(a%c+b%c)%c

另外还要考虑动规的递推公式，这道题很简单，就是：

steps[i]=steps[i-1]+steps[i-2]+steps[i-3];

意思也就是在 i 阶阶梯时，可能是从i-1，i-2，i-3阶上来的，这些位置的登梯方法之和就是i 阶阶梯的登梯方法方案数。
初始条件，0，1，2，3阶需要直接列出。
先上代码和结果：

class Solution {
public:
    int waysToStep(int n) {
        vector<int> steps(n+3);
        steps[0]=0;
        steps[1]=1;
        steps[2]=2;
        steps[3]=4;
        for(int i=4;i<=n;i++)
        {
            steps[i]=(steps[i-3]+steps[i-2])%1000000007;
            steps[i]=(steps[i]+steps[i-1])%1000000007;
        }
        return steps[n];
    }
};

运行结果:

原题链接：https://leetcode-cn.com/problems/three-steps-problem-lcci/