### Python实现爬楼梯问题 #### 动态规划解决方案 动态规划的核心思想是将大问题拆分为多个小问题并逐步求解。对于爬楼梯问题，可以通过构建一个数组 `dp` 来记录到达每一级台阶的方法数。具体来说，到达第 `i` 级台阶的方法数等于到达第 `i-1` 和第 `i-2` 台阶方法数之和。 以下是基于动态规划的代码实现： ```python def climbStairs(n): if n == 0 or n == 1: return 1 dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] print(climbStairs(4)) # 输出：5 ``` 此代码的时间复杂度为 \(O(n)\)，空间复杂度也为 \(O(n)\)[^1]。 为了优化空间复杂度，可以仅保留最近两次的结果，而不必保存整个数组： ```python def climbStairs_optimized(n): if n == 0 or n == 1: return 1 prev1, prev2 = 1, 1 for _ in range(2, n + 1): current = prev1 + prev2 prev1, prev2 = prev2, current return prev2 print(climbStairs_optimized(4)) # 输出：5 ``` 该版本的空间复杂度降低至 \(O(1)\)[^1]。 --- #### 记忆化递归解决方案 记忆化递归通过缓存中间结果来避免重复计算。在爬楼梯问题中，我们可以定义一个辅助函数，并利用字典或其他数据结构存储已访问的状态。 以下是基于记忆化递归的代码实现： ```python def climbStairs_recursive(n, memo=None): if memo is None: memo = {} if n in memo: return memo[n] if n == 0 or n == 1: return 1 memo[n] = climbStairs_recursive(n - 1, memo) + climbStairs_recursive(n - 2, memo) return memo[n] print(climbStairs_recursive(4)) # 输出：5 ``` 在此代码中，时间复杂度仍为 \(O(n)\)，但由于引入了额外的数据结构用于存储中间结果，因此空间复杂度也提升到了 \(O(n)\)[^3]。 --- #### 数学公式法（斐波那契数列） 由于爬楼梯问题本质上是一个斐波那契数列的应用场景，可以直接调用斐波那契数列的相关算法解决问题。例如，使用迭代方式快速计算斐波那契数值： ```python def fibonacci_climb_stairs(n): a, b = 1, 1 for _ in range(n): a, b = b, a + b return a print(fibonacci_climb_stairs(4)) # 输出：5 ``` 这种方法同样具有 \(O(n)\) 的时间复杂度和 \(O(1)\) 的空间复杂度[^2]。 --- ### 总结 以上三种方法均能有效解决爬楼梯问题，其中动态规划和数学公式法更适合大规模输入的情况，而记忆化递归则更直观易懂。实际应用时可根据需求选择合适的算法。