Skip to content
LEETFLIX

Climbing Stairs

EasyMathDPRecursion
Solve on LeetCode

Fibonacci in a trench coat. The gentlest possible introduction to dynamic programming.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Constraints

  • —1 <= n <= 45

Examples

Input

n =
2

Output

2

There are two ways to climb to the top: 1 + 1 and 2.

02

Solution

3 approaches · Python and Go. Pick a tab — the walkthrough follows.

Optimal▶ Animated

Fill dp[1..n] left to right; dp[i] = dp[i−1] + dp[i−2].

Start from the base cases and build upward. By the time we compute dp[i], both of its dependencies are already in the table — no recursion, no cache misses, no stack.

Algorithm

  1. If n ≤ 2 return n.
  2. dp[1] = 1, dp[2] = 2.
  3. For i in 3..n: dp[i] = dp[i−1] + dp[i−2].
  4. Return dp[n].
Time
O(n)
Space
O(n)
Solution.py
class Solution:    def climbStairs(self, n: int) -> int:        if n <= 2:            return n        dp = [0] * (n + 1)   # dp[i] = ways to reach step i        dp[1], dp[2] = 1, 2        for i in range(3, n + 1):            dp[i] = dp[i - 1] + dp[i - 2]        return dp[n]
Watch this run

03

Interactive walkthrough

Playing “Bottom-up table”. Edit the input, hit Run, then scrub.

Approach: Bottom-up table

Loading animation…

Up next

#53Maximum Subarray

Medium

Python · Go · Animated