企业官网建设流程全解析

• 教程

本篇选自阿秀 InterviewGuide 仓库「精选力扣 300+ 题目之动态规划」专题（专题目录）。爬楼梯是动态规划（DP）最经典的入门题之一，本文基于原题解析完整还原两种解法，并结合仓库内剑指 Offer 的斐波那契数列、跳台阶等姊妹题，讲透状态定义、转移方程与滚动数组优化的来龙去脉。读完你不仅能独立写出两种可提交的 C++ 解法，还能一眼识别"爬楼梯 + 斐波那契"这一族题目的共同骨架。

一、题目回顾：问题定义与样例分析

假设你正在爬楼梯，需要n阶你才能到达楼顶，每次你可以爬 1 或 2 个台阶，问有多少种不同的方法可以爬到楼顶。注意：给定n是一个正整数。

示例 1：

输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶

示例 2：

输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶

从小样例可以立刻感知规律：到达第 3 阶的方法数 = 到达第 1 阶的方法数（先到第 1 阶再跨 2 阶）+ 到达第 2 阶的方法数（先到第 2 阶再跨 1 阶），即3 = 1 + 2。这正是动态规划递推关系的雏形。

二、为什么说这是一道"很巧妙的题目"：先想清楚递归与状态

原文档作者将这道题称为"其实很巧妙的题目"，巧妙之处在于：它不用存储任何复杂结构，只需要一个一维状态，甚至只需要两个变量就能完成整道题的求解。

2.1 问题的天然递归结构

要到达第i阶，最后一次跨步只有两种可能：从第i-1阶跨 1 阶，或从第i-2阶跨 2 阶。因此设f(i)为到达第i阶的不同方法数，则：

f(i) = f(i-1) + f(i-2)

边界条件为f(1) = 1、f(2) = 2。

这一结论与仓库中剑指 Offer 专题的"跳台阶"完全同构：一只青蛙一次可以跳 1 级也可以跳 2 级，求跳上n级台阶的总跳法，其递归写法在 08-剑指offer.md 中给出：

int jumpFloor(int number) { if(number==1) return 1; if(number==2) return 2; return jumpFloor(number-1) + jumpFloor(number-2); }

该文档同时注明"递归做法，真的很耗时"——因为f(n)会反复计算大量重叠子问题，时间复杂度呈指数级增长。动态规划的价值，就在于把这种自顶向下的重复递归，改写为自底向上的递推填表，用空间换时间。（剑指 Offer No7 斐波那契数列的递归版本同样被标注为"慢得多"，见 07-剑指offer.md。）

2.2 从递归到 DP 的三个要素

对照动态规划的通用套路，本题三要素非常清晰：

下面两个版本正是围绕"如何落地这三点"给出的递进式优化。

三、第一版解法：自底向上的 DP 数组（O(n) 时间 / O(n) 空间）

原文档第一版给出的完整代码如下：

if (n == 0) return 0; if (n == 1) return 1; vector<int> res(n+1, 0); res[1] = 1; res[2] = 2; for (int i = 3; i <= n; ++i) { res[i] = res[i - 1] + res[i - 2]; } return res[n];

逐步拆解这段代码：

• 边界兜底：题目保证n是正整数，if (n == 0) return 0;属于防御性写法；if (n == 1) return 1;处理最小合法输入。
• 初始化：vector<int> res(n+1, 0)申请n+1个元素，下标0不使用（或视为 0 种方法），res[1] = 1、res[2] = 2给出前两个初值。
• 递推填表：从i = 3开始，每个位置只依赖前两个位置，res[i] = res[i-1] + res[i-2]与上面推导的转移方程一一对应。
• 返回结果：res[n]即最终答案。

复杂度分析

• 时间复杂度：O(n)，单层循环从 3 遍历到 n，每轮 O(1) 加法。
• 空间复杂度：O(n)，需要长度为n+1的辅助数组。

原文档记录的当时提交结果为"执行用时 4 ms，击败 67.85% 的用户；内存消耗 8.5 MB，击败 35.19% 的用户"。需要注意的是，这是当年的 LeetCode 评测快照，仅用于展示"数组版在内存上并不占优"这一事实，不代表当前在线评测环境的数据。

四、第二版解法：滚动变量压缩到 O(1) 空间

观察转移方程res[i] = res[i-1] + res[i-2]可以发现：计算任意一个位置时，真正用到的只有紧邻的前两个值，更早的结果用完即弃。因此完全可以用两个变量滚动推进，这就是原文档"稍微改进一下"的第二版：

int climbStairs(int n) { if (n == 1) { return 1; } int first = 1; int second = 2; for (int i = 3; i <= n; i++) { int third = first + second; first = second; second = third; } return second; }

关键点拆解：

• 初始状态：first = 1对应f(1)，second = 2对应f(2)。
• 滚动更新：每轮先用third = first + second求出当前f(i)，随后把second赋给first、把third赋给second，实现"丢弃最旧值、保留最新两个值"。
• 循环终点：从i = 3循环到n，结束时second恰好就是f(n)；当n == 2时不进入循环，直接返回second = 2，逻辑同样成立。

复杂度对比

原文档记录的当时提交结果为"执行用时 4 ms，击败 67.85% 的用户；内存消耗 8.2 MB，击败 81.26% 的用户"，可见在耗时相同的前提下，滚动变量版的内存占用明显下降（8.5 MB → 8.2 MB）。这一对比恰好演示了动态规划优化的核心方向之一：把"记录所有状态"压缩为"只保留必要状态"。

五、串联仓库姊妹题：爬楼梯的本质是斐波那契数列

5.1 与斐波那契数列的关系

将爬楼梯的序列f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=8...与斐波那契数列F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5...对比即可发现：

f(n) = F(n+1)

两者满足完全相同的递推关系g(i) = g(i-1) + g(i-2)，只是起始项不同。仓库中剑指 Offer No7 斐波那契数列（07-剑指offer.md）给出了与本题第二版几乎同构的滚动实现：

int Fibonacci(int n) { if( n == 0) return 0; if( n == 1) return 1; int first = 0, second = 1, third = 1; for(int i = 2; i <= n; ++i){ third = first + second; first = second; second = third; } return third; }

剑指 Offer No8 跳台阶（08-剑指offer.md）的二刷总结更是直接点题——"其实就是斐波那契数列"。

5.2 仓库内的同族变式题目

掌握了f(i) = f(i-1) + f(i-2)这一核心骨架后，仓库动态规划专题中还有三道"爬楼梯系"变式值得一并刷掉：

• 剑指 Offer No9 变态跳台阶（09-剑指offer.md）：一次可跳 1 到 n 级，推导可得f(n) = 2 * f(n-1)，最终答案退化为2^(n-1)，从"线性递推"升级为"幂次规律"。
• LeetCode 746 使用最小花费爬楼梯（746.使用最小花费爬楼梯.md）：给每一阶加上体力花费cost[i]，求到达顶部的最小花费，转移方程变为res[i] = min(res[i-1], res[i-2]) + cost[i]；其第二版用res[(i-1)%3]、res[(i-2)%3]的取模滚动数组把空间压到 O(1)，是"滚动思想"更工程化的写法。
• LeetCode 62 不同路径（62.不同路径.md）：把一维"台阶"升级为二维"网格"，dp[i][j] = dp[i-1][j] + dp[i][j-1]，是爬楼梯递推思想在二维空间的自然延伸，可作为进阶练习。

六、总结：这道题在面试中考察什么

面试官考 70 爬楼梯，核心想确认三件事：

1. 能否识别最优子结构：能说出"到达第 i 阶只依赖前两阶"，即找到了f(i) = f(i-1) + f(i-2)的转移方程；
2. 能否处理边界：n = 1返回 1、n = 2返回 2 的初始化是否完备；
3. 是否有优化意识：能否从 O(n) 空间数组自然过渡到 O(1) 滚动变量，这恰好对应原文档两个版本"第一版 → 第二版"的演进路径。

建议的刷题闭环是：先按第一版理解填表过程 → 再按第二版写滚动变量 → 最后横向刷掉 746、62 不同路径以及剑指 Offer No7/No8/No9 等姊妹题，把"斐波那契一族"一次性吃透。本题作为动态规划专题的 Easy 起点（专题难度分级见 introduce.md），非常适合作为校招/社招算法复习的第一块基石。

• 教程