在算法入门与动态规划（DP）的殿堂里，LeetCode爬楼梯斐波那契数列问题（第70题）是一座无可争议的里程碑。这道题的核心价值，远不止于教会你计算爬上楼梯的方法数，而在于它以一种极其直观的方式，揭示了动态规划的核心思想——将复杂问题分解为重叠子问题，并通过记忆化或递推避免重复计算，同时完美展现了斐波那契数列在现实建模中的神奇应用。理解这道题，就意味着你抓住了动态规划最本质的“状态定义”与“状态转移”，这是解决无数更复杂优化问题的基石。作为鳄鱼Java的资深内容编辑，我将为你从多维度拆解这道经典题目，探索其从暴力递归到极致优化的完整思维链路。
一、问题重述与建模：如何将生活场景转化为数学模型？
题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？
示例：
- n = 2： 两种方法：(1+1) 或 (2)。
- n = 3： 三种方法：(1,1,1), (1,2), (2,1)。
关键建模：
让我们定义 dp[n] 为“爬上第 n 阶楼梯的不同方法总数”。这是我们解决问题的状态定义。
思考最后一步：要到达第 n 阶，你只能从以下两个位置过来：
1. 从第 n-1 阶爬 1 个台阶上来。
2. 从第 n-2 阶爬 2 个台阶上来。
因此，到达第 n 阶的方法数，等于到达第 n-1 阶的方法数与到达第 n-2 阶的方法数之和。因为你最后一步的选择是独立的，且覆盖了所有可能性。
这就引出了我们的状态转移方程：dp[n] = dp[n-1] + dp[n-2]
同时，我们需要基础情况（Base Case）：
- `dp[0] = 1`： 从地面到第0阶（可以理解为起点）有一种方法，即“不动”。这能使递推式对 n=2 也成立。
- `dp[1] = 1`： 爬到第1阶，只有一种方法（爬1步）。
至此，一个现实问题被完美地转化为一个带有初始条件的递推数列问题，而这正是LeetCode爬楼梯斐波那契数列得名的缘由。
二、递归解法的困境：直观但低效的陷阱
根据上述递推关系，最直接的实现是递归。
```java class Solution { public int climbStairs(int n) { if (n <= 1) return 1; // dp[0]=1, dp[1]=1 return climbStairs(n-1) + climbStairs(n-2); } } ```
复杂度分析：
- **时间复杂度：O(2^n)**。这是一棵深度为 n 的递归树，每个节点分裂为两个子节点，产生了指数级的重复计算。例如，计算 `climbStairs(5)` 会重复计算 `climbStairs(3)` 多次。
- **空间复杂度：O(n)**。递归调用栈的深度。
这种方法在 n 稍大（如 n=45）时就会超时。它清晰地展示了什么是“重叠子问题”——`dp[n-2]` 等在计算 `dp[n]` 和 `dp[n-1]` 时被重复计算。这正是动态规划要解决的核心痛点。
三、动态规划：自底向上的递推（记忆化）
为了消除递归的重复计算，我们使用一个数组（或哈希表）来存储（记忆）已经计算过的子问题的解。有两种实现方式：
1. 记忆化递归（自顶向下）： 在递归的基础上加入缓存。
2. 迭代递推（自底向上）： 从小问题开始，逐步推导到大问题。这是更常见、更高效的DP实现。
迭代DP的Java实现：
```java class Solution { public int climbStairs(int n) { if (n <= 1) return 1; int[] dp = new int[n + 1]; // dp数组，dp[i]表示爬到第i阶的方法数 // 初始化基础情况 dp[0] = 1; dp[1] = 1; // 状态转移：从第2阶开始，递推到第n阶 for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; // 核心状态转移方程 } return dp[n]; } } ```
复杂度分析：
- **时间复杂度：O(n)**。我们只需进行一次从 2 到 n 的线性遍历。
- **空间复杂度：O(n)**。用于存储长度为 n+1 的 dp 数组。
这个解法已经能够高效通过LeetCode测试。它完美体现了动态规划的标准流程：定义状态 -> 设定初始状态 -> 建立状态转移方程 -> 迭代计算。在鳄鱼Java社区的动态规划专题中，这是讲解“重叠子问题”和“最优子结构”时必用的入门案例。
四、斐波那契数列的本质联系与数学洞察
仔细观察我们的状态转移方程和初始条件：
`dp[0]=1, dp[1]=1, dp[n] = dp[n-1] + dp[n-2] (n >= 2)`
这正是斐波那契数列（Fibonacci Sequence）的定义！只不过经典的斐波那契数列通常以 `F(0)=0, F(1)=1` 开始。我们的爬楼梯数列是其一个偏移：`climbStairs(n) = Fib(n+1)`。
这一数学联系至关重要：
1. **揭示了问题的本质结构**：许多看似不同的问题（如铺瓷砖、硬币组合的特定情况）最终都归结为斐波那契数列。
2. **提供了更优的数学工具**： 理论上，我们可以使用斐波那契数列的通项公式（比内公式）在 O(1) 时间和空间内求解。但由于公式涉及浮点数运算和幂次，在整数计算中可能存在精度问题，在编程竞赛和面试中不常用，但知其存在能拓宽视野。
3. **强化了建模思维**： 遇到新问题时，可以思考其解空间是否也呈现出类似的递推关系。
因此，LeetCode爬楼梯斐波那契数列这个关键词精准地指出了此题在算法与数学上的双重重要性。
五、空间优化：从O(n)到O(1)的终极优化
观察状态转移方程 `dp[i] = dp[i-1] + dp[i-2]`，我们发现当前状态 `dp[i]` 只依赖于前两个状态 `dp[i-1]` 和 `dp[i-2]`。我们完全没有必要保存整个 dp 数组，只需要用两个变量滚动记录前两个状态即可。
“滚动数组”思想实现：
```java class Solution { public int climbStairs(int n) { if (n <= 1) return 1; // 初始化：代表dp[0]和dp[1] int prevPrev = 1; // 代表dp[i-2]，初始为dp[0] int prev = 1; // 代表dp[i-1]，初始为dp[1] int current = 0; // 代表dp[i]
for (int i = 2; i <= n; i++) {
current = prev + prevPrev; // 计算dp[i]
// 滚动更新，为下一次迭代做准备
prevPrev = prev; // 下一轮的dp[i-2]就是当前的dp[i-1]
prev = current; // 下一轮的dp[i-1]就是当前的dp[i]
}
// 循环结束时，prev就是dp[n]
return prev;
}
}
<p>更简洁的写法：</p>
<p>```java
public int climbStairs(int n) {
int a = 1, b = 1;
for (int i = 2; i <= n; i++) {
int sum = a + b;
a = b;
b = sum;
}
return b;
}
```</p>
<p><strong>复杂度分析</strong>：<br>
- **时间复杂度：O(n)**。仍然需要线性次计算。<br>
- **空间复杂度：O(1)**。只使用了常数个变量。这是该问题在时间和空间上的最优平衡解，也是面试中最受期待的答案。</p>
<h2>六、举一反三：变种问题与思维扩展</h2>
<p>掌握了基础模型后，可以挑战一系列变种问题，它们会修改“一步能爬的台阶数”或增加新的约束，从而深化对DP思想的理解。</p>
<p><strong>1. 每次可以爬 1、2 或 3 个台阶</strong>：<br>
状态转移方程变为：`dp[n] = dp[n-1] + dp[n-2] + dp[n-3]`，基础情况需要定义 `dp[0]`, `dp[1]`, `dp[2]`。空间优化需要三个变量滚动。</p>
<p><strong>2. 每次可以爬的台阶数是一个数组 `steps`</strong>： 例如 `steps = [1, 3, 5]`。<br>
状态转移方程变为：`dp[n] = sum(dp[n - step])`，其中 `step` 属于 `steps` 且 `n-step >= 0`。这已非常接近“完全背包”问题的模型。</p>
<p><strong>3. 带障碍的爬楼梯（LeetCode 63. 不同路径 II 的简化版）</strong>： 如果某些台阶被标记为障碍不可踩，那么到达该台阶的方法数就是0，转移时需要判断。</p>
<p><strong>4. 最小花费爬楼梯（LeetCode 746）</strong>： 这是动态规划的另一个经典入门题。`cost[i]` 表示踏上第 i 阶楼梯需要支付的费用。状态可以定义为 `dp[i]` 表示到达第 i 阶（并支付 cost[i]）的最小花费，或者定义为到达第 i 阶顶部（即支付完 cost[i] 后）的最小花费。状态转移涉及最小化选择。</p>
<p>所有这些变种，其核心思维框架不变：<strong>定义状态，思考最后一步的所有可能选择，根据选择写出状态转移方程，处理好边界条件</strong>。在鳄鱼Java社区的动态规划专题训练中，这种从简单到复杂的阶梯式训练是快速掌握DP的关键。</p>
<h2>总结与思考</h2>
<p><strong>LeetCode爬楼梯斐波那契数列</strong>问题，如同一把精巧的钥匙，为我们打开了动态规划与组合数学的大门。它教会我们的，不仅仅是一个数列的计算，而是<strong>如何将问题分解为阶段和状态，如何找到状态之间的递推关系，以及如何通过优化存储来提升效率</strong>的通用方法论。</p>
<p>现在，请你思考：如果楼梯不是线性的，而是一个网格（如 LeetCode 62. 不同路径），你能否运用相似的“最后一步”分析法来定义状态和方程？当问题增加约束条件（如“不能连续爬两个2阶”），你该如何调整状态定义来容纳这个新信息？动态规划的强大之处，就在于其思维模型的可扩展性。从爬楼梯出发，你可以逐步攻克更复杂的背包问题、序列问题、图论中的最短路径问题。如果你希望系统性地构建自己的动态规划知识体系，欢迎深入探索鳄鱼Java社区的算法专栏，那里有从这道简单题延伸出去的、完整的问题图谱与实战解析。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
