面试题 08.01. 三步问题

面试题 08.01. 三步问题

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

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

示例 2:

输入：n = 5
 输出：13

提示:

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

思路

类似上楼梯，优化为 O1 空间记录 dp，每次求和防止溢出对结果模 1000000007。

解答

/**
 * @param {number} n
 * @return {number}
 */
var waysToStep = function (n) {
  if (n <= 2) return n;
  else if (n === 3) return 4;
  let a = 1,
    b = 2,
    c = 4,
    d;
  while (--n >= 3) {
    d = (((a + b) % 1000000007) + c) % 1000000007;
    a = b;
    b = c;
    c = d;
  }
  return c;
};