Core pattern

Recursion · DP: counting ways up a staircase

Learn the recursion · dp pattern through one picture you won’t forget, worked on Climbing Stairs.

The example problem

You are climbing a staircase with n steps. Each move you climb either 1 or 2 steps. In how many different ways can you reach the top?

Input:  n = 6
Output: 13

Picture it

Picture the staircase with a number written on each step: the number of different ways to stand on that step. Your last move onto step i came either from step i − 1 (a 1-step) or from step i − 2 (a 2-step). So the ways to reach step i are the two numbers below it added together. We fill the steps from the bottom up.

The key idea

ways[i] = ways[i − 1] + ways[i − 2]: the Fibonacci pattern. Only the last two numbers are needed. O(n).

Python

def climb(n):
    ways = [1, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]
    return ways[n]

Practise recursion · dp

NeetCode 150 problems that use it

1-D DP · 2-D DP · Backtracking ·