《Hello 算法》带约束爬楼梯用状态扩展恢复无后效性的动态规划实战【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇围绕《Hello 算法》hello-algo中“带约束爬楼梯”这一动态规划经典变体展开在“每步可上 1 阶或 2 阶、但不能连续两轮跳 1 阶”的约束下经典的一维状态转移方程会失效。读完本篇你将理解如何通过扩展状态定义引入“上一轮跳了几阶”这一维度重新满足无后效性、推导新的状态转移方程并掌握该算法在 Python、C、C 多语言实现中的完整写法与手工验证方法。一、问题定义为什么经典爬楼梯的 DP 公式会失效仓库在动态规划问题特性章节中给出了“带约束爬楼梯”的完整题面给定一个共有 $n$ 阶的楼梯你每步可以上 $1$ 阶或者 $2$ 阶但不能连续两轮跳 $1$ 阶请问有多少种方案可以爬到楼顶对比无约束版本每次跳 1 阶或 2 阶、求方案总数经典解法是$$dp[i] dp[i-1] dp[i-2]$$其成立的前提是无后效性给定当前状态 $i$后续演化只与 $i$ 本身有关与“如何到达 $i$”无关。而加入“不能连续跳 1 阶”约束后这一点被破坏了——如果你站在第 $i$ 阶上一轮是跳 1 阶上来的本轮只能跳 2 阶上一轮是跳 2 阶上来的本轮跳 1 阶或 2 阶都可以。也就是说下一步选择不仅由“当前在第几阶”决定还取决于“上一轮怎么跳的”。dp[i-1]里混杂了大量“上一轮跳 1 阶”的方案这些方案中本轮再跳 1 阶的部分是非法的因此dp[i] dp[i-1] dp[i-2]直接失效。上图直观展示了这一点爬上第 3 阶仅剩 2 种可行方案其中“连续三次跳 1 阶”的方案111因违反约束被舍弃。二、状态扩展把“上一轮跳了几阶”纳入状态解决这类问题的通用手段是扩展状态定义让状态携带足够的历史信息使问题重新满足无后效性。本书采用二维状态$$dp[i, j] \triangleq \text{处在第 } i \text{ 阶且上一轮跳了 } j \text{ 阶 的方案数},\quad j \in {1, 2}$$在此定义下可以精确推导状态转移方程若本轮跳了 1 阶到达第 $i$ 阶即状态 $[i, 1]$由于不能连续跳 1 阶上上一轮必然跳了 2 阶只能从第 $i-1$ 阶且上一轮跳 2 阶的状态转移而来$$dp[i, 1] dp[i-1, 2]$$若本轮跳了 2 阶到达第 $i$ 阶即状态 $[i, 2]$上上一轮跳 1 阶或 2 阶都合法可从第 $i-2$ 阶的两个状态转移而来$$dp[i, 2] dp[i-2, 1] dp[i-2, 2]$$合并写作$$ \begin{cases} dp[i, 1] dp[i-1, 2] \ dp[i, 2] dp[i-2, 1] dp[i-2, 2] \end{cases} $$最终答案取 $dp[n, 1] dp[n, 2]$爬到第 $n$ 阶时上一轮无论跳 1 阶还是 2 阶都合法两者之和即为方案总数。初始状态的含义代码中对最小子问题的预设需要特别注意这是该题容易写错的地方初始状态取值含义dp[1][1]1到达第 1 阶且上一轮跳 1 阶方案[1]合法dp[1][2]0一步跳 2 阶无法落在第 1 阶无解dp[2][1]0到达第 2 阶且上一轮跳 1 阶方案只能是[1, 1]连续两轮跳 1 阶违反约束dp[2][2]1到达第 2 阶且上一轮跳 2 阶方案[2]合法同时当 $n \in {1, 2}$ 时直接返回 1——这两种情况下唯一合法方案分别是[1]与[2]。三、Python 完整实现关联文档 climbing_stairs_constraint_dp.md 是 Python 实现 的 Python Tutor 单步可视化入口文件内容即该函数的编码后源码与驱动代码。其完整可运行实现如下与仓库源码逐行一致def climbing_stairs_constraint_dp(n: int) - int: 带约束爬楼梯动态规划 if n 1 or n 2: return 1 # 初始化 dp 表用于存储子问题的解 dp [[0] * 3 for _ in range(n 1)] # 初始状态预设最小子问题的解 dp[1][1], dp[1][2] 1, 0 dp[2][1], dp[2][2] 0, 1 # 状态转移从较小子问题逐步求解较大子问题 for i in range(3, n 1): dp[i][1] dp[i - 1][2] dp[i][2] dp[i - 2][1] dp[i - 2][2] return dp[n][1] dp[n][2] Driver Code if __name__ __main__: n 9 res climbing_stairs_constraint_dp(n) print(f爬 {n} 阶楼梯共有 {res} 种方案)实现要点说明dp 表形状为(n1) × 3第一维存楼梯阶数 $i$第二维存“上一轮跳的阶数” $j \in {1, 2}$由于 Python 索引从 0 开始j 0列仅作占位这也是数组宽度取 3 的原因C 实现中对应calloc(3, sizeof(int))。填表顺序为自底向上的迭代for i in range(3, n 1)从第 3 阶开始逐阶推导每阶的两个状态只依赖 $i-1$ 与 $i-2$ 两行的结果保证了被引用的状态均已计算完毕。驱动代码取 $n 9$运行输出爬 9 阶楼梯共有 9 种方案与手工推演一致见下一节。仓库的批量测试脚本 test_all.py 会逐个运行chapter_*/下的 Python 文件该文件的正确性因此被持续验证。手工推演n 9 的 dp 表按上述转移方程手工填表可以得到完整的中间过程idp[i][1]上一轮跳 1 阶dp[i][2]上一轮跳 2 阶合计110120113112411251236224723583479459以 $i 4$ 为例验证到达第 4 阶且上一轮跳 1 阶只能从 $dp[3][2] 1$ 转移而来对应方案[2, 1, 1]的末段……准确说是上一轮为 1 阶的[2, 1, 1]序列到达第 4 阶且上一轮跳 2 阶来自 $dp[2][1] dp[2][2] 0 1 1$方案[1, 1, 2]非法被自动排除[2, 2]合法。枚举第 4 阶的全部合法走法恰好是[2, 2]与[1, 2, 1]两种与合计值 2 吻合。最终 $dp[9][1] dp[9][2] 4 5 9$与驱动代码输出一致。四、C 与 C 实现中的同一算法核心同一算法在仓库的多语言实现中保持逐语句对应便于对比各语言处理二维表的方式。C 版本climbing_stairs_constraint_dp.c需要手工管理内存二维表通过“指针数组 逐行分配”构造/* 带约束爬楼梯动态规划 */ int climbingStairsConstraintDP(int n) { if (n 1 || n 2) { return 1; } // 初始化 dp 表用于存储子问题的解 int **dp malloc((n 1) * sizeof(int *)); for (int i 0; i n; i) { dp[i] calloc(3, sizeof(int)); } // 初始状态预设最小子问题的解 dp[1][1] 1; dp[1][2] 0; dp[2][1] 0; dp[2][2] 1; // 状态转移从较小子问题逐步求解较大子问题 for (int i 3; i n; i) { dp[i][1] dp[i - 1][2]; dp[i][2] dp[i - 2][1] dp[i - 2][2]; } int res dp[n][1] dp[n][2]; // 释放内存 for (int i 0; i n; i) { free(dp[i]); } free(dp); return res; }C 版本climbing_stairs_constraint_dp.cpp则用vector免除手工释放/* 带约束爬楼梯动态规划 */ int climbingStairsConstraintDP(int n) { if (n 1 || n 2) { return 1; } // 初始化 dp 表用于存储子问题的解 vectorvectorint dp(n 1, vectorint(3, 0)); // 初始状态预设最小子问题的解 dp[1][1] 1; dp[1][2] 0; dp[2][1] 0; dp[2][2] 1; // 状态转移从较小子问题逐步求解较大子问题 for (int i 3; i n; i) { dp[i][1] dp[i - 1][2]; dp[i][2] dp[i - 2][1] dp[i - 2][2]; } return dp[n][1] dp[n][2]; }三种实现的算法核心完全一致相同的边界处理$n \le 2$ 返回 1、相同的初始状态、相同的转移方程仅容器构造方式Python 列表推导 / C 手动malloccalloc/ Cvector嵌套构造不同。这体现了动态规划代码的典型特征——状态定义与转移方程是算法本体容器细节只是语言层面的工程差异。五、复杂度分析与空间优化方向时间复杂度 $O(n)$填表循环执行 $n-2$ 次每次完成两个状态的常数时间更新。空间复杂度 $O(n)$dp 表规模为 $(n1) \times 3$。从源码结构看dp[i][1]仅引用第 $i-1$ 行、dp[i][2]仅引用第 $i-2$ 行即每轮最多依赖前 2 行结果因此理论上可以像仓库中无约束版本的滚动变量写法参考 climbing_stairs_dp.py 里的climbing_stairs_dp_comp那样只保留最近两行做滚动压缩将空间降至 $O(1)$。这里按教程“先建立完整 dp 表、便于观察状态”的原则保留二维写法。六、延伸思考状态扩展的边界在哪里本书在讲解完本题后紧接着给出了一个对照组问题——“爬楼梯与障碍生成”爬到第 $i$ 阶时系统会在第 $2i$ 阶放上障碍物之后所有轮都不允许再跳上第 $2i$ 阶。其差异在于带约束爬楼梯后效性只依赖前一个状态上一轮跳了几阶扩展一维状态即可消除DP 依然高效障碍生成问题每一次跳跃都在更高阶梯上遗留障碍未来决策依赖过去所有状态状态空间随路径爆炸从源码与文档的论述看动态规划对此类问题往往无能为力需要转向启发式搜索等其他方法。因此本题的价值不仅在于“会做这一题”而在于掌握一条判断准则当无后效性被破坏时先检查“缺失的历史信息”是否有限且低维——若是扩展状态维度恢复无后效性若依赖全部历史则 DP 可能不再是合适的工具。小结“带约束爬楼梯”的约束不能连续跳 1 阶破坏了经典方程 $dp[i] dp[i-1] dp[i-2]$ 的无后效性前提解法是将状态扩展为 $dp[i, j]$第 $i$ 阶 上一轮跳 $j$ 阶转移方程为 $dp[i,1] dp[i-1,2]$、$dp[i,2] dp[i-2,1] dp[i-2,2]$答案为 $dp[n,1] dp[n,2]$初始状态需体现约束$dp[1][1]1$、$dp[2][2]1$而“上一轮跳 1 阶到达第 2 阶”的方案[1,1]非法故 $dp[2][1]0$驱动示例 $n9$ 的输出为 9 种方案可依据上表逐行手工验证时间 $O(n)$、空间 $O(n)$由于每行只依赖前两行滚动压缩至 $O(1)$ 空间是可行的优化方向。更多上下文可继续阅读动态规划问题特性章节本题是其“无后效性”小节的配套实现以及练习中“爬楼梯的方案数”基础题无约束一维 DP两者配合可完整覆盖从经典爬楼梯到带约束变体的学习路径。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考