动态规划解爬楼梯问题：从递归到空间优化-云帆数科

1. 爬楼梯问题与动态规划的天然契合第一次看到LeetCode 70题爬楼梯时很多人会下意识地用递归暴力破解——这确实能得到正确答案但效率低得可怕。直到某次面试中当面试官要求我计算爬100级台阶的方法数时我才真正理解动态规划DP在这个问题中的精妙之处。这个问题描述很简单假设你正在爬楼梯每次可以跨1或2个台阶。问到达第n级台阶有多少种不同的方法当n2时有(11)和(2)两种方法n3时有(111, 12, 21)三种。看起来像是组合数学问题但DP给出了更优雅的解法。为什么DP特别适合这类问题因为爬楼梯满足DP的两个核心性质最优子结构到达第n阶的方法数取决于n-1和n-2阶的方法数重叠子问题计算f(n)需要重复计算f(n-1)、f(n-2)等关键理解把有多少种走法的问题转化为最后一步是从哪来的决策问题。这是DP思维的关键转折点。2. 从暴力递归到记忆化搜索的演进路径2.1 递归解法及其缺陷最直观的解法是递归def climbStairs(n): if n 1: return 1 if n 2: return 2 return climbStairs(n-1) climbStairs(n-2)这个解法虽然正确但时间复杂度是O(2^n)——因为每次调用都会分裂成两个子调用。计算climbStairs(40)可能需要几分钟2.2 记忆化搜索优化通过添加缓存来存储已计算结果memo {} def climbStairs(n): if n in memo: return memo[n] if n 1: return 1 if n 2: return 2 memo[n] climbStairs(n-1) climbStairs(n-2) return memo[n]时间复杂度立即降为O(n)因为每个n值只计算一次。这是DP的雏形但递归调用栈仍有O(n)空间开销。2.3 空间复杂度的隐藏陷阱即使使用记忆化当n10000时递归解法仍会爆栈。这是很多人在面试中容易忽略的点递归解法在理论上是正确的但在工程实践中可能不可行。这是为什么要掌握迭代DP写法的重要原因。3. 标准动态规划解法的实现细节3.1 状态定义与转移方程DP的核心是明确dp[i]的定义到达第i阶的方法数状态转移方程dp[i] dp[i-1] dp[i-2]边界条件dp[1]1, dp[2]23.2 迭代实现def climbStairs(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)。这是最标准的DP写法清晰展现了DP的核心要素。3.3 空间优化技巧观察发现dp[i]只依赖前两个状态因此可以优化为def climbStairs(n): if n 2: return n a, b 1, 2 for _ in range(3, n1): a, b b, ab return b空间复杂度降为O(1)。这是面试官最希望看到的写法。4. 动态规划的本质与思维训练4.1 为什么这不是斐波那契数列虽然数学形式相同但两者的物理意义完全不同斐波那契f(0)0, f(1)1爬楼梯dp[0]无意义dp[1]1, dp[2]2算法题重要的是问题建模能力而不是死记硬背公式。这是很多刷题新手容易犯的错误。4.2 DP与分治法的区别两者都涉及子问题分解但关键差异在于分治法子问题互不重叠如归并排序DP子问题大量重叠需要记忆化4.3 如何识别DP适用问题当问题具有以下特征时考虑DP求最大/最小值或方案总数问题可以分解为子问题子问题之间存在重叠具有最优子结构性质5. 变种问题与实际应用场景5.1 步长变化的扩展如果每次可以走1、2或3步解法只需修改转移方程dp[i] dp[i-1] dp[i-2] dp[i-3]5.2 带障碍的爬楼梯LeetCode 91某些台阶不可踏足时只需在转移时判断if obstacle[i] 1: dp[i] 0 else: dp[i] dp[i-1] dp[i-2]5.3 最小花费爬楼梯LeetCode 746dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])5.4 实际工程应用机器人路径规划游戏角色移动逻辑金融中的期权定价模型编译器中的指令调度6. 常见错误与调试技巧6.1 边界条件处理新手常犯的错误忘记处理n0的情况dp数组大小误设为n而非n1初始化时漏掉dp[2]的情况6.2 空间优化时的陷阱当使用滚动变量优化空间时# 错误写法 a b b a b # 此时a已经是新的b值 # 正确写法 a, b b, a b6.3 大数测试用例当n很大时如1e5需要注意Python默认递归深度限制通常1000整数溢出问题Python无此问题但其他语言需考虑结果取模要求如题目要求结果mod 1e977. 从爬楼梯到DP思维的进阶之路理解爬楼梯问题后可以尝试这些经典DP问题最长递增子序列LIS背包问题系列编辑距离股票买卖问题打家劫舍系列每道题都体现了不同的状态定义技巧一维状态爬楼梯二维状态编辑距离带维度状态背包问题状态机股票问题我在准备算法面试时会专门记录每种状态定义的模式这比死记硬背代码有效得多。比如爬楼梯这类线性DP问题状态定义通常是以i结尾的某种性质而转移方程往往只涉及前几个状态。

企业数字化 ERP 产品动态

相关推荐

Pi Agent框架运行时源码全解析：一次任务从进来到落地的完整链路

先把结论放在前面：这篇笔记的主角是 Pi Agent 框架的运行时部分，上一篇我把框架的模块边界和入口启动流程捋了一遍，这篇把重点放在“一次任务进来之后，框架内部到底怎么跑的”这个问题上。也就是你把这个框架拿去做二次开发之前&a… · 2026/11/2 12:18:19

四人智力竞赛抢答器硬件设计：基于74系列芯片的闭环控制系统

简介：本资源为西华大学《四人智力竞赛抢答器》课程设计完整说明书，面向电子类、自动化及嵌入式方向本科生与课程设计初学者，解决多路抢答信号锁存、优先判别、声光指示、倒计时控制与分数动态管理等典型数字系统设计问题。压缩包含1个857KB的… · 2026/11/2 12:18:19

Mac上安装配置MuJoCo与robosuite的完整实践指南

最开始看别人在Linux上装MuJoCo和robosuite，总觉得没什么难度：一条pip install，再复制个demo跑起来就完事了。但真正在Mac上动手，就是另一回事了。Homebrew莫名装不上，conda换源之后又碰上渲染窗口直接闪退&#xff0c… · 2026/11/3 19:03:50

微服务架构下基于Nacos的轻量级任务调度方案设计与实现

1. 项目背景与核心问题在微服务架构中，任务调度系统是不可或缺的基础组件。XXL-JOB作为国内广泛使用的开源调度系统，以其稳定性和功能完整性赢得了大量用户的青睐。然而，在全面采用NacosSpring Cloud Alibaba技术栈的架构中，我们发… · 2026/11/4 21:12:16

MMORPG服务端3.2.2本地搭建：认证、世界服与数据库排错

3.2.2 这个版本号，在游戏服务端研究的圈子里算是一个绕不开的坐标。它处在客户端协议还没有大规模加密、服务端模拟框架的文档相对完整、社区沉淀下来的调试经验也足够多的那个时间段，所以很多人想弄明白“一个 MMORPG 的服务端到底是怎么跑起来的”&… · 2026/11/4 21:12:16

AI智能理论到工程实践：泛化、缩放定律与排查方法

“AI智能的理论的概述”这个说法，第一次看到的时候我愣了几秒。它不像一本教材的目录，也不像某个具体技术的名字，更像是有人想把一整套关于智能的假设、模型和边界条件塞进一句话里。我在这个方向待了十来年，从最早手推感知机的权… · 2026/11/4 21:12:16

系统音频捕获+实时字幕翻译：LiveCaptions-Translator 实战配置与避坑指南

实时语音翻译这件事，我前后折腾过不下五套方案，从最早的手动转录加翻译拼接，到后来的本地模型串联，再到现成的桌面工具，踩过的坑能写满两页纸。LiveCaptions-Translator 是我目前留在机器上长期使用的一套，… · 2026/11/4 21:12:16

Linux 上 Miniconda 安装配置全攻略：环境隔离与避坑指南

1. 为什么我不推荐直接用系统自带的 Python 很多人第一次在 Linux 上装 Python 环境，习惯性敲 sudo apt install python3 ，装完发现版本是系统仓库里那个老掉牙的 3.8 或者 3.10，然后 pip 装包时各种权限报错，最后被迫 sudo pi… · 2026/11/4 21:12:16

N4系统集成避坑：协议矩阵、Device点数与BACnet IP开放

简介：《N4系统集成介绍-2021.pdf》面向楼宇自控、弱电集成与IBMS对接人员，聚焦霍尼韦尔N4平台在BA系统及第三方设备接入中的架构理解与接口开放选型。文档以NIAGARA4集成架构为主线，梳理冷热源、空调、变配电、电扶梯、能源计费、消防、智能照… · 2026/11/4 21:11:14

双极步进电机控制实战：DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49