#70

Easy

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Climbing Stairs

Climbing Stairs is a classic dynamic programming problem where you calculate distinct ways to reach the top using step transitions.

math dynamic programming memoization

Problem Statement

You are given a staircase with n steps, and you can climb either 1 or 2 steps at a time. Determine how many distinct sequences of steps will take you to the top, emphasizing the dynamic programming pattern where each state depends on previous states.

For example, given n = 3, the possible ways to climb are [1,1,1], [1,2], and [2,1]. Constraints require 1 <= n <= 45, and you should focus on leveraging memoization or iterative DP to compute results efficiently.

Examples

Example 1

Input: n = 2

Output: 2

There are two ways to climb to the top.

1 step + 1 step
2 steps

Example 2

Input: n = 3

Output: 3

There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

Constraints

1 <= n <= 45

Solution Approach

Recursive with Memoization

Define a helper function that returns the number of ways to reach step k. Use memoization to store results for each step to avoid redundant recursion. Base cases are step 0 and step 1. The transition is f(k) = f(k-1) + f(k-2), directly reflecting the allowed step sizes.

Iterative Dynamic Programming

Use a DP array dp[0..n] where dp[i] stores the number of ways to reach step i. Initialize dp[0] = 1, dp[1] = 1. Iteratively fill dp[i] = dp[i-1] + dp[i-2]. This approach avoids recursion overhead and is simple to implement for the state transition pattern.

Optimized Space Using Two Variables

Instead of an array, keep only two variables representing previous two steps. Update iteratively using temp = prev1 + prev2. This reduces space complexity to O(1) while still adhering to the same transition f(n) = f(n-1) + f(n-2).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for iterative or memoized DP, since each step is computed once. Space complexity is O(n) for the DP array or memoization table, reducible to O(1) with two-variable optimization. The recurrence ensures linear growth without recomputation.

What Interviewers Usually Probe

Asks for the number of ways to reach step n using allowed steps.
Hints at using previous step results, indicating dynamic programming pattern recognition.
Tests understanding of optimizing space from DP array to constant variables.

Common Pitfalls or Variants

Common pitfalls

Attempting plain recursion without memoization leads to exponential time complexity.
Confusing step sequences, double-counting combinations instead of counting distinct paths.
Ignoring base cases or incorrectly initializing dp array, causing off-by-one errors.

Follow-up variants

Changing allowed steps to 1, 2, or 3 alters the state transition and requires adjusting the DP recurrence.
Finding minimum steps to reach the top instead of counting distinct ways changes the problem to a min-path DP variant.
Adding constraints like broken steps introduces conditional checks in the transition formula.

FAQ

What is the recurrence relation for Climbing Stairs?

The number of ways to reach step n is f(n) = f(n-1) + f(n-2), reflecting the allowed step sizes of 1 or 2.

Can Climbing Stairs be solved using pure recursion?

Yes, but without memoization, recursion has exponential time complexity and will fail for larger n.

How can I reduce space in the DP solution?

Keep only the last two computed values and update iteratively to reduce space from O(n) to O(1).

What is the time complexity of iterative DP for Climbing Stairs?

Iterative DP runs in O(n) time since each step is calculated exactly once using previous results.

How does the problem exemplify state transition dynamic programming?

Each step depends on previous states, making f(n) a direct sum of f(n-1) and f(n-2), the core state transition pattern.

terminal

Solution

Solution 1: Recursion

We define $f[i]$ to represent the number of ways to climb to the $i$-th step, then $f[i]$ can be transferred from $f[i - 1]$ and $f[i - 2]$, that is:

1

2

3

4

5

6

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return b

Solution 2: Matrix Quick Power to Accelerate Recursion

We set $Fib(n)$ to represent a $1 \times 2$ matrix $\begin{bmatrix} F_n & F_{n - 1} \end{bmatrix}$, where $F_n$ and $F_{n - 1}$ are the $n$-th and $(n - 1)$-th Fibonacci numbers respectively.

1

2

3

4

5

6

class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return b

Continue Practicing

#241 different ways to add parentheses #464 can i win #509 fibonacci number