LeetCode爬楼梯问题：DFS解法超时，求更优解决方案

Hey there! Let's break down why your DFS approach is timing out for n=35 and walk through way more efficient solutions that'll fix this problem.

First, let's get to the root of the DFS issue: your recursive code is solving the exact same subproblems over and over again. For example, when calculating climbStairs(5), you'll recalculate climbStairs(3) multiple times—once when breaking down climbStairs(4) and once directly from climbStairs(3) itself. This leads to a time complexity of O(2^n), which gets completely out of hand as n grows: 2^35 is over 34 billion operations. No wonder it's hitting the time limit!

Here are three optimized approaches that blow DFS out of the water:

1. Memoized DFS (Top-Down Dynamic Programming) #

This is the simplest tweak to your existing code—we just add a cache to store results of subproblems we've already solved, so we never waste time computing them twice.

In Python, you can use the built-in lru_cache decorator for this quick win:

from functools import lru_cache

class Solution:
    @lru_cache(maxsize=None)
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

• Time Complexity: O(n) — we compute each climbStairs(k) exactly once.
• Space Complexity: O(n) — for the recursion stack and the cache storage.

2. Bottom-Up Dynamic Programming (Space-Optimized) #

Instead of starting from n and working downward, we start from the base cases and build our way up to n. Even better, we don't need to store the entire DP array—we only need the last two values at each step to compute the next one.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        # Base cases: ways to climb 1 step = 1, ways to climb 2 steps = 2
        prev_two = 1
        prev_one = 2
        for i in range(3, n + 1):
            current = prev_one + prev_two
            prev_two = prev_one
            prev_one = current
        return prev_one

• Time Complexity: O(n) — single linear pass from 3 to n.
• Space Complexity: O(1) — we only use a handful of variables, no extra arrays or recursion stack.

3. Fibonacci Formula (O(log n) Time) #

Did you catch the pattern? The number of ways to climb n stairs is exactly the (n+1)-th Fibonacci number (if we define F(1)=1, F(2)=1, F(3)=2...). We can use Binet's formula to compute this in logarithmic time (thanks to efficient exponentiation under the hood).

import math

class Solution:
    def climbStairs(self, n: int) -> int:
        sqrt_5 = math.sqrt(5)
        fib_n = math.pow((1 + sqrt_5)/2, n + 1) - math.pow((1 - sqrt_5)/2, n + 1)
        return int(fib_n / sqrt_5)

• Time Complexity: O(log n) — since computing powers can be done in logarithmic time.
• Space Complexity: O(1) — just a few math operations, no extra storage needed.

A quick note: For extremely large n, floating-point precision might become an issue, but for LeetCode's constraints (n ≤ 45), this works perfectly.

Which One Should You Pick? #

• If you want to keep your recursive structure with minimal changes: Go with memoized DFS.
• If you want the best space efficiency: Bottom-up DP is your go-to.
• If you want the fastest possible runtime (for very large n): The Fibonacci formula is unbeatable.

All of these will handle n=35 (and even n=1000) in a fraction of a second, unlike your original DFS approach.

内容的提问来源于stack exchange，提问作者Kurt Peek