三步问题

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

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

  • 输入：n = 5
    输出：13

1
2
3
4
5
6
7
8
var waysToStep = function(n) {
    const mod = 1000000007;
    const dp = [null, 1, 2, 4];
    for (let i = 4; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
    }
    return dp[n];
};