How do you solve Climbing Stairs on LeetCode?

Climbing Stairs (LeetCode #70) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The number of ways to reach the nth step can be derived from the sum of the ways to reach the (n-1)th and (n-2)th steps.

What is the brute force solution for Climbing Stairs?

The brute force approach for Climbing Stairs is Brute Force, with O(2^n) time complexity and O(n) space complexity. The brute force approach involves recursively exploring all possible ways to climb the stairs by either taking 1 step or 2 steps at a time. This method can lead to a lot of repeated calculations, making it inefficient for larger values of n. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Climbing Stairs?

Climbing Stairs uses the following concepts: Math, Dynamic Programming, Memoization. The recommended patterns to study are: Dynamic Programming, Recursion.

What are the interview tips for Climbing Stairs?

Always start with a brute force solution to understand the problem before optimizing. Be clear about your base cases and how they affect the recursive or iterative solution. Discuss your thought process and how you arrived at the optimal solution during the interview.

What are common mistakes when solving Climbing Stairs?

Not considering the base cases correctly, especially for small values of n. Forgetting to initialize the dp array properly in the optimal solution.

#70

Climbing Stairs

Easy

MathDynamic ProgrammingMemoizationDynamic ProgrammingRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(2^n)	O(n)
Space	O(n)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses dynamic programming to store the number of ways to reach each step, building up from the base cases. This avoids redundant calculations and reduces the time complexity significantly.

⚙️

Algorithm

4 steps

1Step 1: Create an array dp of size n + 1 to store the number of ways to reach each step.
2Step 2: Initialize dp[0] = 1 and dp[1] = 1 (base cases).
3Step 3: Loop from 2 to n, and for each step, set dp[i] = dp[i - 1] + dp[i - 2].
4Step 4: Return dp[n] as the result.

solution.py8 lines

1def climbStairs(n):
2    if n == 1:
3        return 1
4    dp = [0] * (n + 1)
5    dp[0], dp[1] = 1, 1
6    for i in range(2, n + 1):
7        dp[i] = dp[i - 1] + dp[i - 2]
8    return dp[n]

ℹ

Complexity note: The time complexity is linear because we compute the number of ways for each step exactly once. The space complexity is also linear due to the dp array.

1The number of ways to reach the nth step can be derived from the sum of the ways to reach the (n-1)th and (n-2)th steps.
2This problem exhibits overlapping subproblems, making it suitable for dynamic programming.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.