#07MediumAlgorithms · 55% acceptance

Counting Distinct Paths

Dynamic ProgrammingMath

You climb a staircase of `n` steps, taking 1 or 2 steps at a time. Return the number of distinct ways to reach the top.

The recurrence is the whole lesson: ways(n) = ways(n-1) + ways(n-2). Recognize it and DP stops being scary.

Input: n = 3

Output: 3

Note: 1+1+1, 1+2, and 2+1.

Input: n = 5

Output: 8

solution.pyPython 3

def climb(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Test console

// hit Run to execute the sample tests

// Interactive editor preview. Live code execution arrives with your early-access cohort.