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

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;
}

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;
    }
};

Rust

impl Solution {
    pub fn ways_to_step(n: i32) -> i32 {
        let mut dp = [1, 2, 4];
        let n = n as usize;
        if n <= 3 {
            return dp[n - 1];
        }
        for _ in 3..n {
            dp = [
                dp[1],
                dp[2],
                (((dp[0] + dp[1]) % 1000000007) + dp[2]) % 1000000007,
            ];
        }
        dp[2]
    }
}