Skip to content

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

Solution 1: Recursion

We define $f[i]$ as the number of ways to reach the $i$-th step, initially $f[1]=1$, $f[2]=2$, $f[3]=4$. The answer is $f[n]$.

The recursion formula is $f[i] = f[i-1] + f[i-2] + f[i-3]$.

Since $f[i]$ is only related to $f[i-1]$, $f[i-2]$, $f[i-3]$, we can use three variables $a$, $b$, $c$ to store the values of $f[i-1]$, $f[i-2]$, $f[i-3]$, reducing the space complexity to $O(1)$.

The time complexity is $O(n)$, where $n$ is the given integer. The space complexity is $O(1)$.

1
2
3
4
5
6
7
class Solution:
    def waysToStep(self, n: int) -> int:
        a, b, c = 1, 2, 4
        mod = 10**9 + 7
        for _ in range(n - 1):
            a, b, c = b, c