Easy

Climbing Stairs

011

You are climbing a staircase with n steps. Each move can climb either one or two steps. Return the number of distinct ways to reach the top.

EXAMPLES

Example 1

Input
{
  "n": 3
}

Output
3

FUNCTION SHAPE

n: int→int

SOLUTION NOTE

dp(i) = number of ways to climb i steps. We reach step i from step i-1 (1 step) or step i-2 (2 steps). Base case: dp(0) = dp(1) = 1.

Reveal reference solution +

pythonREFERENCE

def climbStairs(self, n: int) -> int:
    @cache
    def dp(i):
        if i <= 1: return 1
        return dp(i-1) + dp(i-2)
    return dp(n)

TimeO(n)

SpaceO(n)