从爬楼梯到算法世界：动态规划与斐波那契的奇妙邂逅

从爬楼梯到算法世界：动态规划与斐波那契的奇妙邂逅

在算法学习的旅程中，总有一些经典问题让人印象深刻。“爬楼梯问题”就是其中之一，看似简单的题目，却蕴藏了动态规划与斐波那契数列的深刻联系。今天，我就以这个问题为切入点，带大家深入探讨如何通过动态规划解锁更广阔的算法世界。

---

1. 问题描述与分析

问题描述

假设你正在爬一座楼梯，共有n阶，每次你可以选择爬1阶或2阶。问：到达顶楼有多少种不同的爬法？

举个例子：

• 如果有3阶楼梯，你的可能路径是：
  • 1阶+1阶+1阶
  • 1阶+2阶
  • 2阶+1阶
    总共有3种爬法。

分析问题

这个问题本质上是求解一个递归关系：

• 如果你站在第n阶，那么你是从n-1阶迈1步或从n-2阶迈2步到达的。
• 因此，第n阶的爬法数目可表示为：
  $$f(n)=f(n-1)+f(n-2)$$

初始条件：

• 如果楼梯只有1阶，只有一种爬法：$f(1)=1$
• 如果楼梯有2阶，有两种爬法：$f(2)=2$

聪明的你可能已经发现了，这正是斐波那契数列的定义公式！

---

2. 解法探索

我们来看看不同的解法，从递归到动态规划，再到优化。以代码为例，每种解法都蕴含了对问题不同层次的思考。

---

方法一：递归解法（Naive Approach）

这是最直观的实现，但存在巨大的性能瓶颈。

def climb_stairs_recursive(n):"""递归解法，计算爬楼梯的方法数"""if n <= 2:return n  # 边界情况return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

问题：

• 这种方法的时间复杂度是指数级的（$O(2^n)$），因为存在大量重复计算。
• 比如计算f(5)时，需要重复计算f(4)和f(3)，效率极低。

---

方法二：记忆化递归（优化递归）

为了解决重复计算的问题，我们可以利用一个数组或字典来缓存中间结果。

def climb_stairs_memoization(n, memo={}):"""记忆化递归，减少重复计算"""if n in memo:return memo[n]if n <= 2:return n  # 边界情况memo[n] = climb_stairs_memoization(n - 1, memo) + climb_stairs_memoization(n - 2, memo)return memo[n]

优势：

• 通过缓存中间结果，将时间复杂度降低到了$O(n)$。
• 但仍然使用了递归，函数栈会占用一定的内存。

---

方法三：动态规划（Bottom-Up Approach）

动态规划是一种自底向上的方法，通过数组存储每一阶的爬法数，避免递归的栈开销。

def climb_stairs_dp(n):"""动态规划解法"""if n <= 2:return n  # 边界情况dp = [0] * (n + 1)  # 初始化DP数组dp[1], dp[2] = 1, 2  # 初始条件for i in range(3, n + 1):  # 逐步计算每一阶的爬法数dp[i] = dp[i - 1] + dp[i - 2]return dp[n]

优势：

• 时间复杂度是$O(n)$。
• 空间复杂度是$O(n)$，因为需要额外数组存储每一阶的结果。

---

方法四：动态规划的空间优化

进一步优化空间，利用滚动变量替代数组。毕竟我们每次只需要用到前两阶的结果。

def climb_stairs_optimized(n):"""动态规划 + 空间优化"""if n <= 2:return n  # 边界情况prev1, prev2 = 1, 2  # 初始化前两阶的爬法数for _ in range(3, n + 1):  # 从第三阶开始计算curr = prev1 + prev2prev1, prev2 = prev2, curr  # 滚动更新return prev2

优势：

• 时间复杂度是$O(n)$。
• 空间复杂度降至$O(1)$，非常高效。

---

3. 从爬楼梯到斐波那契：算法的深远意义

在解决爬楼梯问题时，我们不仅用到了递归与动态规划，还触碰到了算法的“哲学”内核：

1. 化繁为简：将复杂问题分解为小问题，通过递归或迭代求解。
2. 优化思维：从朴素递归到记忆化，再到动态规划和空间优化，反映了算法不断进化的过程。
3. 广泛应用：斐波那契数列及其变种在动态规划中有着极为广泛的应用，如股票买卖、最长子序列等。

---

4. 举一反三：实战小题目

爬楼梯问题可以扩展为更多实际场景：

• 不同步数的爬楼梯：每次可以爬1、2或3阶，如何修改代码解决？
• 路径统计：假设楼梯每阶有个性化通行费用，如何找到代价最低的路径？

例如，每次可选择1、3、5阶，代码如下：

def climb_stairs_varied_steps(n, steps):"""通用爬楼梯解法"""dp = [0] * (n + 1)dp[0] = 1  # 到达第0阶的方式只有一种for i in range(1, n + 1):dp[i] = sum(dp[i - step] for step in steps if i - step >= 0)return dp[n]

---

结语：从爬楼梯到算法巅峰

爬楼梯问题虽小，却涵盖了递归、动态规划、滚动数组等算法的精髓。在算法学习的过程中，我们不仅需要解决问题，更要透过问题看到本质。这道题目告诉我们：从解决问题的简单方法开始，不断优化，就能更接近算法的美和极致。