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

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

示例1:

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

示例2:

 输入：n = 5
 输出：13

提示:

  1. n范围在[1, 1000000]之间 
//动态规划问题，a[2]=2, a[3]=4, a[4]=a[3]+a[2]+a[1];a[i]=a[i-1]+a[i-2]+a[i-3];
//可以得到递推式为a[i]=a[i-1]+a[i-2]+a[i-3];
#include <iostream>
#include <cstdio>
#define ll long long
class Solution {
public:
    ll a[1000005] = {};
    int waysToStep(int n) {
    a[0] = 1;
    for (int i=1;i<=n;i++) {
        if (i-1>=0) {
            a[i]+=a[i-1];
        }
        if (i-2>=0) {
            a[i]+=a[i-2];
        }
        if (i-3>=0) {
            a[i]+=a[i-3];
        }
        a[i] = a[i]%1000000007;
    }
    return a[n];
    }
};