Climbing Stairs - Video Solutions
Climbing Stairs - Dynamic Programming - Leetcode 70 - Python
Climbing Stairs - Video Solution
Watch 10 video solutions for Climbing Stairs, a easy level problem involving Math, Dynamic Programming, Memoization. This walkthrough by NeetCode has 853,397 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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?
Example 1:
Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
Example 2:
Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step
Constraints:
1 <= n <= 45
Approach Overview
Problem Overview: You are given n stairs. Each move allows either 1 step or 2 steps. The task is to compute the total number of distinct ways to reach the top. This is a classic recurrence problem where the number of ways to reach step i depends on the previous two steps.
Approach 1: Recursive with Memoization (Time: O(n), Space: O(n))
The recurrence relation is straightforward: to reach step n, you either come from step n-1 with a single step or from step n-2 with a double step. That leads to ways(n) = ways(n-1) + ways(n-2). A naive recursive solution recomputes the same subproblems repeatedly, resulting in exponential time. Memoization fixes this by storing results in a cache (array or hash map) and returning the stored value when the function encounters the same input again.
This turns the recursion into a top‑down dynamic programming solution. Each state is computed exactly once, giving O(n) time complexity and O(n) space for the memo table plus recursion stack. This approach is useful when you want to express the solution directly from the recurrence and let memoization handle repeated work.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(n), Space: O(n))
The same recurrence can be solved iteratively. Create a DP array where dp[i] represents the number of ways to reach step i. Initialize the base cases: dp[1] = 1 and dp[2] = 2. Then iterate from 3 to n, computing dp[i] = dp[i-1] + dp[i-2]. Each iteration builds on previously computed states.
This bottom‑up dynamic programming approach avoids recursion and stack overhead. The recurrence is identical to the Fibonacci sequence, which is why this problem frequently appears in discussions of math patterns in DP problems. The algorithm performs a single pass through the array, giving O(n) time and O(n) space.
The space can also be optimized to O(1) by keeping only the last two values instead of the entire array. Since each state depends only on the previous two, two variables are sufficient to compute the sequence iteratively.
Recommended for interviews: Interviewers expect the dynamic programming interpretation. Starting with the recursive recurrence shows you understand the problem structure, especially if you mention memoization to eliminate repeated work. The strongest answer moves quickly to the bottom‑up DP or constant‑space Fibonacci-style iteration because it demonstrates recognition of the pattern and optimal implementation.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n) | O(n) | When expressing the recurrence naturally with recursion and caching subproblems |
| Dynamic Programming (Bottom-Up) | O(n) | O(n) or O(1) optimized | Preferred iterative solution for interviews and production code |