从斐波那契到爬楼梯：用Python动态规划解决经典问题，附LeetCode 70题保姆级解析

从斐波那契到爬楼梯用Python动态规划解决经典问题附LeetCode 70题保姆级解析每次看到LeetCode上那些标着简单却让人抓耳挠腮的题目总让我想起自己初学算法时的窘迫。特别是第70题爬楼梯表面看是个小学数学题实则暗藏玄机。今天我们就来拆解这个经典问题看看它如何与斐波那契数列产生奇妙关联以及如何用动态规划优雅解决。1. 问题本质与数学建模站在楼梯前的小明可能不知道他面临的其实是个历史悠久的数学问题。当台阶数n10时走法总数恰好是斐波那契数列的第11项如果从F(0)1开始计数。这种巧合背后是相同的递推关系F(n) F(n-1) F(n-2)为什么这个公式成立想象你站在第n级台阶上上一步只能来自从n-1级跨1步从n-2级跨2步这两种选择互斥且完备因此总方法数就是两者之和。这就是重叠子问题特性——每个台阶的解都依赖于更小台阶的解。边界条件需要特别注意n1时只有1种走法[1]n2时有2种走法[1,1]和[2]用表格表示前几项的关系台阶数n12345走法数F(n)123582. 从递归到动态规划的进化新手最容易想到的递归解法虽然直观但存在严重性能问题def climb_stairs(n): if n 1: return 1 if n 2: return 2 return climb_stairs(n-1) climb_stairs(n-2)这个解法的时间复杂度是O(2^n)因为每次调用都会分裂成两个子调用。当n40时计算量已经超过万亿次。动态规划通过存储中间结果来优化def climb_stairs(n): if n 2: return n dp [0]*(n1) dp[1], dp[2] 1, 2 for i in range(3, n1): dp[i] dp[i-1] dp[i-2] return dp[n]此时时间复杂度降为O(n)空间复杂度也是O(n)。但观察状态转移可以发现我们只需要保存前两个状态def climb_stairs(n): if n 2: return n a, b 1, 2 for _ in range(3, n1): a, b b, ab return b这种优化将空间复杂度降至O(1)是面试官最期待的写法。3. 复杂度分析与数学解法除了动态规划这个问题还有几种有趣的解法矩阵快速幂时间复杂度O(log n) 利用斐波那契的矩阵表示通过快速幂算法加速计算def matrix_pow(mat, power): result [[1,0],[0,1]] while power 0: if power % 2 1: result matrix_mult(result, mat) mat matrix_mult(mat, mat) power // 2 return result def climb_stairs(n): if n 2: return n mat [[1,1],[1,0]] return matrix_pow(mat, n)[0][0]通项公式法时间复杂度O(1) 斐波那契数列有精确的闭式解F(n) (φ^n - ψ^n)/√5 其中φ(1√5)/2≈1.618, ψ(1-√5)/2≈-0.618Python实现import math def climb_stairs(n): sqrt5 math.sqrt(5) phi (1 sqrt5) / 2 return int((phi**(n1) - (-phi)**(-n-1))/sqrt5)注意浮点数精度限制使得这种方法在n70时可能产生误差4. 变种问题与实际应用掌握了基础解法后可以尝试这些常见变种1. 步长变化如果还能一次跨3步递推式变为F(n)F(n-1)F(n-2)F(n-3)def climb_stairs(n): if n 2: return n if n 3: return 4 a, b, c 1, 2, 4 for _ in range(4, n1): a, b, c b, c, abc return c2. 成本最小化每个台阶有体力成本求最小成本路径def min_cost_climbing(costs): n len(costs) dp [0]*n dp[0], dp[1] costs[0], costs[1] for i in range(2, n): dp[i] min(dp[i-1], dp[i-2]) costs[i] return min(dp[-1], dp[-2])3. 空间约束在O(1)空间下处理大规模n值使用生成器def fib_gen(): a, b 0, 1 while True: yield a a, b b, ab这些变种在电商优惠券组合、机器人路径规划等领域都有实际应用。比如优惠券满减问题就可以建模为用给定面额的券组合出目标金额的方法数。5. 调试技巧与常见错误在实现动态规划时这些陷阱需要注意边界条件错误忘记处理n0或n1的情况索引偏移Python列表从0开始与问题描述的从1开始容易混淆空间优化遗漏没有发现只需要前两个状态的规律整数溢出当n很大时结果可能超过普通整数范围调试时可以打印dp表格检查中间结果用小规模测试用例手动验证比较递归和迭代版本的结果# 调试示例 def test(): for n in range(1, 10): recursive climb_stairs_recursive(n) dp climb_stairs_dp(n) assert recursive dp, fFailed at n{n} print(All tests passed!)6. LeetCode实战与优化针对LeetCode 70题提交时要注意预处理前几个结果加速使用位运算代替模运算循环展开减少迭代次数优化后的终极版本def climb_stairs(n): if n 3: return n a, b 2, 3 for _ in range(4, n1): a, b b, a b return b对于特别大的n比如1e18需要使用快速幂算法或者找规律发现周期性。我在一次周赛中遇到过n上限为1e100的变种题最终通过观察斐波那契数列模某个数的周期性解决了问题。