机考刷题系列第一篇我选了 LeetCode 70 爬楼梯。这题在 LeetCode 上难度是简单但它在机考里出现的频率相当高尤其适合刚接触算法刷题的人拿来建立动态规划的直觉。题目一句话就能说清假设你正在爬楼梯需要 n 阶才能到楼顶每次只能爬 1 阶或 2 阶问有多少种不同的方法可以爬到楼顶。真正值得琢磨的不是答案本身而是为什么这个问题会自动和斐波那契数列扯上关系以及它在机考环境里到底有哪些坑。这篇文章会把完整思路、代码写法、机考输入输出区别、常见变体和踩坑经验一次性讲清楚。不管你是在牛客网刷题还是在公司笔试平台上被 ACM 式输入输出折磨过这篇都能给你一个可以直接照抄的答案模板。1. 先搞懂题目在问什么1.1 把“爬楼梯”翻译成状态转移用 f(n) 表示爬上 n 阶楼梯的方法数。它为什么能构成递推关键是看最后一步你要到第 n 阶只可能是从第 n-1 阶跨 1 级上来或者从第 n-2 阶跨 2 级上来。不可能有第三种情况因为每次只能走 1 阶或 2 阶。所以爬上 n 阶的方法数就是“到第 n-1 阶的方法数”加上“到第 n-2 阶的方法数”f(n) f(n-1) f(n-2)这就是斐波那契数列的递推式。很多人在这一步会卡住总觉得应该乘起来才对。这里要分清到 n-1 阶和到 n-2 阶是两种互斥的走法互斥的情况用加法。只有“先做 A 再做 B”这种前后依赖关系才用乘法。你最后一步不可能同时既跨 1 级又跨 2 级所以它们不可能同时发生。边界条件也很直观1 阶楼梯只有 1 种走法2 阶楼梯有 2 种走法要么一次跨 2 阶要么分两次各跨 1 阶。所以 f(1)1f(2)2。有的写法会用 f(0)1, f(1)1 作为初始值这样从 n2 开始递推f(2) 自动等于 2。两种初始化在结果上完全等价但如果你在机考时一会儿用这套一会儿用那套最容易在 n1 或 n2 这种小边界上翻车。我的建议是统一用 f(0)1, f(1)1因为这样循环从 2 开始写代码结构最干净边界不用单独判断。1.2 为什么这题是机考的“黄金入门题”我见过不少公司的笔试题第一道就是爬楼梯或者它的亲戚。原因很简单它考察你能不能快速识别递推结构。一个候选人如果连爬楼梯都写不顺后面的动态规划题大概率也拿不下来。反过来这题要是能在 10 分钟内写完并通过说明基础递推和代码落地能力是过关的。更关键的是它是一道“可升级”的题。随便改一个条件就变成另一道经典题把“问方法数”改成“求最小花费”就是 LeetCode 746 使用最小花费爬楼梯把“每次能爬 1 或 2 阶”改成“每次能爬 1/2/3 阶”递推式立刻变成三项相加要求输出结果对 1e97 取模又成了笔试里的常规操作。所以第一个刷它不只是为了学会这一题而是为了把这一题的模板记牢后面遇到变体直接套。2. 解法演进从指数级到 O(n)2.1 暴力递归先知道它为什么不行最容易想到的写法是直接递归代码只有三行def climbStairs(n): if n 2: return n return climbStairs(n - 1) climbStairs(n - 2)这段代码在 n5 时很快但你试到 n40 就会发现明显卡顿n45 基本跑不动。原因是它把一个子问题重复算了很多遍。递归调用树的每一层都会分裂成两个节点整棵树几乎是满二叉树时间复杂度是 O(2^n) 级别的指数增长。n50 的时候这个数字大到任何机器都扛不住。有一种错误认知是“机考不会出这么大的数据”。别赌。LeetCode 70 的隐藏测试用例 n 上限是 45暴力递归在临界点附近已经非常勉强。真实笔试平台数据范围更不可控而且就算递归没超时Python 默认递归深度也只有 1000 左右n 一大直接 RecursionError。所以暴力递归只适合用来理解问题不适合当最终答案。2.2 记忆化搜索把重复计算的结果存下来递归的问题在于同一个子问题被反复算。比如 f(10) 会被 f(11) 和 f(12) 分别调用而这两个调用又各自引出一整棵子树。解决办法很笨也很有效加一个字典缓存算过的结果直接存起来下次要的时候查表返回。memo {} def climbStairs(n): if n 2: return n if n in memo: return memo[n] memo[n] climbStairs(n - 1) climbStairs(n - 2) return memo[n]这样每个 n 只会真正计算一次时间复杂度降为 O(n)。这是“自顶向下”的思路也是动态规划里“重叠子问题”这个概念最直观的演示。如果你在机考现场突然忘了递推代码怎么写先写一版记忆化搜索也能拿分只是它还会有递归深度的问题。2.3 自底向上动态规划机考里最稳的写法更稳的做法是反过来从最小的子问题开始往上推。开一个长度为 n1 的数组按顺序填 f(1)、f(2)、f(3)……直到 f(n)。这就是标准的自底向上动态规划。def climbStairs(n): if n 1: return 1 dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]填表过程可以手动验证一遍n5 时dp[2]2dp[3]3dp[4]5dp[5]8。答案是 8正好是斐波那契数列的第 6 项。这个结果可以当成自测标准代码写完随手心算几个小 n 对一下比干瞪眼找 bug 高效得多。但你会发现整个递推过程中dp[i] 只依赖 dp[i-1] 和 dp[i-2]数组前面那些值后面用不到了。这时候就可以做空间压缩把数组换成两个变量。这个优化必须学会因为后续很多动态规划题都能用它把 O(n) 空间压成 O(1)。3. 机考实战各语言写法与输入输出细节3.1 滚动数组写法详解我把最推荐的 Python 写法摆出来这就是你以后遇到同类题的第一反应模板def climbStairs(n: int) - int: if n 1: return 1 prev, cur 1, 1 for _ in range(2, n 1): prev, cur cur, prev cur return cur这段代码里prev 代表 f(i-2)cur 代表 f(i-1)。每轮循环计算新的 f(i)prevcur然后同步更新。Python 的多变量赋值会先计算右边再整体赋值所以不需要临时变量这点很方便。初始状态 prevcur1 对应 f(0)f(1)1循环从 i2 开始n 就是最终 cur。空间复杂度 O(1)时间复杂度 O(n)。LeetCode 官方题解给的也是这套思路。机考的时候只要题目不要求输出路径、不要求记录到达每一阶的中间结果一律用这个版本不要用数组版本。数组版本在 LeetCode 上能过但有些笔试平台的测试数据更大省内存的写法永远更稳。3.2 LeetCode 模式和 ACM 模式的区别这里有个大坑很多只在 LeetCode 上刷过题的人第一次参加机考会懵。LeetCode 的模式是“核心代码模式”系统已经帮你处理好了输入你只需要补全函数体。比如上面写的 climbStairs 函数直接提交就行。但不少公司笔试、牛客网的机考用的是“ACM 模式”也就是自己写 main 函数、自己读输入、自己控制输出格式。同样的题你要多写一层输入处理import sys def climbStairs(n: int) - int: if n 1: return 1 prev, cur 1, 1 for _ in range(2, n 1): prev, cur cur, prev cur return cur def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) print(climbStairs(n)) if __name__ __main__: main()sys.stdin.read().strip().split() 是笔试场景里最稳的读法因为它能一次性把缓冲区里的所有字符吃掉然后按空白符切成列表不管输入是一行还是多行都不怕。比 input() 更抗干扰。注意输出要换行吗print 默认就是换行不用额外处理。Java 版本也顺手给出来Java 笔试碰到这种题很常见import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); System.out.println(climbStairs(n)); } public static long climbStairs(int n) { if (n 1) return 1; long prev 1, cur 1; for (int i 2; i n; i) { long temp cur; cur prev cur; prev temp; } return cur; } }为什么用 long 不用 int因为斐波那契数列增长极快n45 时结果已经是 1836311903接近 int 上限。如果题目把 n 加到 70int 直接溢出。笔试里养成用 long 的习惯能避免一部分隐蔽错误。3.3 取模问题什么时候取、怎么取有些笔试会要求输出对 10000000071e97取模的结果处理办法是在每次相加后立刻取模def climbStairs_mod(n: int, MOD: int 10**9 7) - int: if n 1: return 1 prev, cur 1, 1 for _ in range(2, n 1): prev, cur cur, (prev cur) % MOD return cur注意是循环体内每一轮都取模不是算完最后再取一次。原因有两个第一不加中间取模的话n 一大 Java/C 的 long 也可能溢出溢出之后计算结果已经错了最后取模也救不回来第二取模运算保证了中间结果始终在可控范围内。Python 没有溢出问题但这个习惯要在写 Java/C 时提前养成。提示1e97 是质数且接近 int 最大值是笔试最常用的模数。如果题目没写取模要求就别多此一举直接返回原值。4. 进阶解法n 大到 1e18 时怎么办4.1 矩阵快速幂机考第一题通常不会出到 n1e18但组合笔试里后面几道题可能升级。一旦 n 大起来O(n) 的循环也不够用这时候要上矩阵快速幂。斐波那契递推可以写成矩阵形式[f(n) ] [1 1] [f(n-1)] [f(n-1)] [1 0] * [f(n-2)]记矩阵 M [[1, 1], [1, 0]]那么[f(n1), f(n)]^T M^n * [f(1), f(0)]^T求 M 的 n 次方用快速幂能把时间复杂度降到 O(log n)。核心是矩阵乘法和快速幂模板Python 可以这样写def mat_mul(a, b): return [ [(a[0][0] * b[0][0] a[0][1] * b[1][0]) % MOD, (a[0][0] * b[0][1] a[0][1] * b[1][1]) % MOD], [(a[1][0] * b[0][0] a[1][1] * b[1][0]) % MOD, (a[1][0] * b[0][1] a[1][1] * b[1][1]) % MOD] ] def mat_pow(mat, power): res [[1, 0], [0, 1]] while power: if power 1: res mat_mul(res, mat) mat mat_mul(mat, mat) power 1 return res def climbStairs_fast(n: int) - int: if n 1: return 1 m mat_pow([[1, 1], [1, 0]], n) return m[0][0] # 这对应 f(n1)当 f(0)0 时需要微调需要注意初始值定义不同矩阵幂的返回结果对应哪一项很容易搞混。我个人的验证技巧是算出 n5 时矩阵幂的第 0 行第 0 列是不是 8如果是说明矩阵方向和初始条件配对正确。这个不要求你在普通机考里手写但你要知道有这么个东西看到 n 巨大的题不至于当场懵。4.2 通项公式为什么不推荐斐波那契还有一个通项公式也叫比内公式是用黄金比例和它的共轭算出来的f(n) (φ^n - ψ^n) / √5其中 φ (1√5)/2ψ (1-√5)/2。看起来算个幂就能出结果实际在机考里是陷阱。问题出在浮点精度double 类型只有 15 到 16 位有效数字n 一大φ^n 的整数部分就会有误差再除以 √5 再取整很可能错一位。LeetCode 早期有人用这个方法在 Python 里通过是因为 Python 浮点运算有一定容错但 n 超过 70 就开始不稳到 n100 基本不能看。机考环境里任何涉及浮点数的精确计数题都要优先避免。老老实实用整数递推或矩阵快速幂不要为了秀公式冒险。5. 机考高频变体和常见问题排查实录5.1 变体一表速查爬楼梯这题在笔试里经常戴个不同马甲出现核心用法都是动态规划。我把常见的几个变体整理在下面变体名称递推变化考察重点使用最小花费爬楼梯dp[i] min(dp[i-1], dp[i-2]) cost[i]状态转移的“取最值”变体每次能爬 1/2/3 阶dp[i] dp[i-1] dp[i-2] dp[i-3]转移项数变化带禁止点的楼梯禁止的 i 处 dp[i] 0条件判断控制状态输出对 1e97 取模每轮相加后取模大数运算处理n 极大1e18改用矩阵快速幂算法结构升级看到这些变体不要慌它们的骨架完全一样先明确 dp[i] 的含义再写转移方程再定边界条件最后决定要不要做空间压缩。爬楼梯模板吃透了这类题等于送分。5.2 常见错误速查表下面这五个错误我在别人代码里和自己笔试里都见过列出来省得你再踩一遍错误现象根本原因解决方法n1 时返回 0边界条件写错把 f(1)1 丢了初始化 dp[0]dp[1]1n45 本地直接卡死用了未优化的暴力递归改成自底向上循环或记忆化Java 结果变负数int 溢出返回类型和中间变量用 long取模结果不对只在最后返回时取模循环体内每轮相加后立刻取模ACM 模式读不到数据用了 input() 但输入有多行用 sys.stdin.read().split()还有一个很有意思的坑是“输出格式多了一个空格”。LeetCode 核心代码模式里你 print 什么东西都无所谓但 ACM 模式里平台会拿你的标准输出和答案做严格比对多一个空格、少一个换行都可能判 WA。每次提交前检查一下代码里有没有调试用的打印语句我已经不止一次见过 print(“cur ”, cur) 忘记删导致全题零分的情况。6. 题后的经验这题我刷过很多遍从第一眼看到递推式到后来不看答案闭眼写滚动数组中间隔的其实就是对“状态”这个概念的理解。后来我用这套模板过掉了大量笔试第一题经验就是每刷完一题在本子上写三行——递推式、边界条件、复杂度。70 题的三行分别是 dp[i]dp[i-1]dp[i-2]、dp[0]dp[1]1、时间 O(n) 空间 O(1)。话很短但比抄十遍代码管用。最后再送一个小技巧。斐波那契数列有几个关键项可以背下来f(5)8f(10)89f(20)10946f(30)1346269。写完代码后输入这几个测一下结果对得上基本就稳了。这个习惯能让你在机考里少浪费很多调试时间后面遇到 746 题、1137 题核心逻辑全都长一个样。