《Hello 算法》带约束爬楼梯：用状态扩展恢复无后效性的动态规划实战

《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 阶”的方案（1+1+1）因违反约束被舍弃。

二、状态扩展：把“上一轮跳了几阶”纳入状态

解决这类问题的通用手段是扩展状态定义，让状态携带足够的历史信息，使问题重新满足无后效性。本书采用二维状态：

$$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 阶都合法，两者之和即为方案总数。

初始状态的含义

代码中对最小子问题的预设需要特别注意，这是该题容易写错的地方：

同时，当 $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} 种方案")

实现要点说明：

1. dp 表形状为(n+1) × 3：第一维存楼梯阶数 $i$，第二维存“上一轮跳的阶数” $j \in {1, 2}$；由于 Python 索引从 0 开始，j = 0列仅作占位，这也是数组宽度取 3 的原因（C 实现中对应calloc(3, sizeof(int))）。
2. 填表顺序为自底向上的迭代：for i in range(3, n + 1)从第 3 阶开始逐阶推导，每阶的两个状态只依赖 $i-1$ 与 $i-2$ 两行的结果，保证了被引用的状态均已计算完毕。
3. 驱动代码取 $n = 9$，运行输出爬 9 阶楼梯共有 9 种方案，与手工推演一致（见下一节）。仓库的批量测试脚本 test_all.py 会逐个运行chapter_*/下的 Python 文件，该文件的正确性因此被持续验证。

手工推演：n = 9 的 dp 表

按上述转移方程手工填表，可以得到完整的中间过程：

以 $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 表，用于存储子问题的解 vector<vector<int>> dp(n + 1, vector<int>(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 手动malloc+calloc/ C++vector嵌套构造）不同。这体现了动态规划代码的典型特征——状态定义与转移方程是算法本体，容器细节只是语言层面的工程差异。

五、复杂度分析与空间优化方向

• 时间复杂度 $O(n)$：填表循环执行 $n-2$ 次，每次完成两个状态的常数时间更新。
• 空间复杂度 $O(n)$：dp 表规模为 $(n+1) \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$；
• 驱动示例 $n=9$ 的输出为 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