README_EN.md

08.01. Three Steps Problem

中文文档

Description

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. The result may be large, so return it modulo 1000000007.

Example1:

 Input: n = 3 

 Output: 4

Example2:

 Input: n = 5

 Output: 13

Note:

1. 1 <= n <= 1000000

Solutions

Python3

class Solution:
    def waysToStep(self, n: int) -> int:
        if n < 3:
            return n
        a, b, c = 1, 2, 4
        for _ in range(4, n + 1):
            a, b, c = b, c, (a + b + c) % 1000000007
        return c

Java

class Solution {
    public int waysToStep(int n) {
        if (n < 3) {
            return n;
        }
        int a = 1, b = 2, c = 4;
        for (int i = 4; i <= n; ++i) {
            int t = a;
            a = b;
            b = c;
            c = ((a + b) % 1000000007 + t) % 1000000007;
        }
        return c;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
 var waysToStep = function(n) {
    if (n < 3) return n;
    let a = 1, b = 2, c = 4;
    for (let i = 3; i < n; i++) {
        [a, b, c] = [b, c, (a + b + c) % 1000000007];
    }
    return c;
};

C++

class Solution {
public:
    int waysToStep(int n) {
        if (n < 3) {
            return n;
        }
        int a = 1, b = 2, c = 4, i = 4;
        while (i++ <= n) {
            int t = ((a + b) % 1000000007 + c) % 1000000007;
            a = b;
            b = c;
            c = t;
        }
        return c;
    }
};