Python实现可变步长爬楼梯：每次走1至m阶的通用解法
深入解析使用Python解决每次可走1至m阶的可变步长爬楼梯问题，提供标准动态规划递推、滑动窗口时间优化与空间压缩的完整通用解法与代码示例。
在经典的爬楼梯问题中，通常限制每次只能跨 1 阶或 2 阶。当规则拓展为单次允许跨越 1 至 m 阶（m ≥ 1）时，目标是计算登上第 n 阶台阶的所有不同走法总数。本文将介绍该问题的通用递推关系，给出标准动态规划实现，并通过维护滑动窗口前缀和将时间复杂度优化至 O(n)，同时系统梳理初始边界与极端条件。
一、问题定义与状态转移关系
假设台阶总级数为 n（非负整数），每次单步跨越的阶数可以是集合 {1, 2, ..., m} 中的任意整数。我们需要求出从地面（第 0 阶）到达第 n 阶的合法走法序列总数。
利用动态规划思想，我们定义状态 dp[i] 为到达第 i 阶台阶的方法总数。考虑到达第 i 阶的“最后一步”：
- 最后一步跨 1 阶：前一个位置只能是第
i-1阶，方案数为dp[i-1]； - 最后一步跨 2 阶：前一个位置只能是第
i-2阶，方案数为dp[i-2]； - ……
- 最后一步跨
k阶（1 ≤ k ≤ m且k ≤ i）：前一个位置是第i-k阶，方案数为dp[i-k]。
因为这些最后跨步的步长互不相同，所形成的走法集合互斥且完备，根据加法原理，到达第 i 阶的总方案数即为最近 m 个可达阶数方案数的总和：
dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-m] (其中所有下标小于 0 的项取值为 0)
初始状态设定为 dp[0] = 1。这代表站在地面的基本状态方案数为 1，也意味着如果一次性直接跨 k 阶到达第 k 阶，它将继承 dp[0] 的这 1 种直接跨入方案。
二、通用动态规划代码实现与逐步计算
按照上述状态转移方程，最直接的算法是使用一个长度为 n + 1 的列表记录每个台阶的方案数。外层循环遍历台阶 i（从 1 到 n），内层循环遍历允许的步长 step（从 1 到 m）。
1. 完整实现代码
def climb_stairs_general(n: int, m: int) -> int:
"""
计算每次最多走 m 阶时，爬到第 n 阶的走法总数。
参数:
n: 目标楼梯阶数 (n >= 0)
m: 单次最大允许跨越的阶数 (m >= 1)
返回:
走法总数
"""
# 边界防御
if n < 0 or m < 1:
return 0
if n == 0:
return 1
# 初始化 dp 数组，dp[i] 表示登上第 i 阶的方法数
dp = [0] * (n + 1)
dp[0] = 1 # 站在地面的初始方案数为 1
# 递推填表
for i in range(1, n + 1):
# 单次跨步最多为 m，但不能超过当前已有的台阶数 i
max_step = min(i, m)
for step in range(1, max_step + 1):
dp[i] += dp[i - step]
return dp[n]
# 示例验证：n = 5, m = 3
if __name__ == "__main__":
test_n, test_m = 5, 3
result = climb_stairs_general(test_n, test_m)
print(f"台阶数 n = {test_n}, 最大步长 m = {test_m} 时，总走法为: {result}")
2. 执行结果输出示例
# 运行输出：
台阶数 n = 5, 最大步长 m = 3 时，总走法为: 13
为了清晰观察状态值的演变过程，我们可以跟踪 n = 5, m = 3 时的计算步骤：
- i = 0: 初始化
dp[0] = 1； - i = 1:
step ∈ [1, min(1, 3)]→dp[1] = dp[0] = 1； - i = 2:
step ∈ [1, min(2, 3)]→dp[2] = dp[1] + dp[0] = 1 + 1 = 2； - i = 3:
step ∈ [1, min(3, 3)]→dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4； - i = 4:
step ∈ [1, 3]→dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7； - i = 5:
step ∈ [1, 3]→dp[5] = dp[4] + dp[3] + dp[2] = 7 + 4 + 2 = 13。
三、关键对比：双重循环累加 vs 滑动窗口维护
为了深入理解算法效率，我们可以对比两种不同的状态更新机制。在相同的输入条件（台阶数 n、最大步长 m）下，实现细节的差异将直接决定时间复杂度是依赖于 m 还是与 m 无关。
| 对比维度 | 标准动态规划（双重循环累加） | 滑动窗口优化动态规划（维护窗口和） |
|---|---|---|
| 计算机制 | 对每个台阶 i，显式循环 1 ~ min(i, m)，逐项求和。 |
维护一个代表最近 m 个台阶和的变量 window_sum，每前进一步仅需一次加法与一次减法。 |
| 时间复杂度 | O(n × m) |
O(n)，与最大步长 m 的大小完全无关。 |
| 空间复杂度 | O(n)（亦可压缩至 O(m)） |
O(n)（亦可压缩至 O(m)） |
| 实现复杂度 | 逻辑直观，不易出错，容易进行边界防护。 | 需要准确处理滑动窗口的“移入新项”与“移出过期项”时机。 |
| 适用场景 | m 较小（如 m ≤ 3）时性能差异不明显。 |
当 m 较大（例如 m = 1000, n = 100000）时，具有绝对性能优势。 |
为什么这种差异至关重要？观察连续两个状态的表达式：
dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-m]
dp[i-1] = dp[i-2] + dp[i-3] + ... + dp[i-m-1]
将两式相减可得：dp[i] - dp[i-1] = dp[i-1] - dp[i-m-1]。整理后得到：
dp[i] = 2 * dp[i-1] - dp[i-m-1]
这意味着求 dp[i] 并不需要重复把 m 个数加一遍，只需在前一项的基础上加上新进窗口的 dp[i-1]，并减去滑出窗口的 dp[i-m-1]。从 O(m) 的求和开销骤降为 O(1) 的更新。
四、滑动窗口优化实现与空间压缩
基于滑动窗口机制，我们可以维护一个全局变量 window_sum，其初始值为 0。当计算到 dp[i] 时，执行以下两步：
- 将刚跨过的上一阶
dp[i-1]加入窗口：window_sum += dp[i-1]； - 如果跨度超出
m（即i - 1 - m ≥ 0），将已经超出步长范围的dp[i - 1 - m]移出窗口：window_sum -= dp[i - 1 - m]； - 此时
window_sum精确等于前m项之和，直接赋值dp[i] = window_sum。
1. 时间优化后的通用代码
def climb_stairs_sliding_window(n: int, m: int) -> int:
"""
基于滑动窗口维护最近 m 项和，实现 O(n) 时间复杂度的通用爬楼梯算法。
"""
if n < 0 or m < 1:
return 0
if n == 0:
return 1
dp = [0] * (n + 1)
dp[0] = 1
window_sum = 0
for i in range(1, n + 1):
# 1. 纳入最新前驱 dp[i-1]
window_sum += dp[i - 1]
# 2. 移除超出最大跨度 m 的过期历史项 dp[i - 1 - m]
if i - 1 - m >= 0:
window_sum -= dp[i - 1 - m]
# 3. 记录当前台阶方案数
dp[i] = window_sum
return dp[n]
2. 空间压缩优化：将空间从 O(n) 降低至 O(m)
观察状态转移可知，我们自始至终只需要保留最近的 m 个历史状态值。如果 n 极大而内存受限，可以使用一个长度为 m 的双端队列（或循环数组）来存储这些状态，使空间复杂度从 O(n) 优化至 O(m)：
from collections import deque
def climb_stairs_space_optimized(n: int, m: int) -> int:
"""
空间复杂度压缩至 O(m) 的滑动窗口解法。
"""
if n < 0 or m < 1:
return 0
if n == 0:
return 1
# 使用固定容量为 m 的双端队列维护最近 m 项
queue = deque([1]) # 对应 dp[0]
window_sum = 1 # 当前队列中的总和
for i in range(1, n + 1):
# 当前台阶方案数就是队列内元素之和
current = window_sum
# 准备为下一个台阶服务：维护窗口
if len(queue) == m:
removed = queue.popleft()
window_sum -= removed
queue.append(current)
window_sum += current
# 循环结束时，最近入队的值即为 dp[n]
return queue[-1]
五、常见边界陷阱与测试验证
在实际工程或面试中，容易因为边界情况导致数组越界或计算结果错误。以下是几个容易被忽略的关键细节：
如果允许单次跨越的最大步长
m 大于或等于总阶数 n，那么在从第 0 阶到第 n 阶之间的任意中间阶梯，都可以选择“落脚”或“不落脚”。共有 n - 1 个中间台阶，每个台阶有选或不选 2 种状态，因此总走法恒等于 2^(n-1)。读者可以利用此性质对算法的输出进行快速自测。
当
m = 1 时，每次只能走 1 阶，无论 n 多大，走法永远只有唯一定义的一种（1+1+...+1）。算法应能自然返回 1。
综合测试用例与验证
def run_tests():
test_cases = [
# (n, m, 预期结果, 说明)
(0, 3, 1, "0 阶台阶，起点方案数为 1"),
(1, 3, 1, "1 阶台阶，只能走 1 步"),
(2, 2, 2, "经典斐波那契走法: [1+1, 2]"),
(3, 2, 3, "经典斐波那契走法: [1+1+1, 1+2, 2+1]"),
(4, 4, 8, "m >= n 时，结果为 2^(4-1) = 8"),
(5, 3, 13, "正文演算实例"),
(10, 1, 1, "m=1 时退化为唯一走法"),
]
for n, m, expected, desc in test_cases:
res_dp = climb_stairs_general(n, m)
res_win = climb_stairs_sliding_window(n, m)
res_opt = climb_stairs_space_optimized(n, m)
assert res_dp == expected == res_win == res_opt, f"测试失败: n={n}, m={m}"
print(f"[通过] n={n:2d}, m={m:2d} -> 结果: {res_dp:2d} ({desc})")
if __name__ == "__main__":
run_tests()
执行上述测试套件，输出结果如下（示例）：
[通过] n= 0, m= 3 -> 结果: 1 (0 阶台阶，起点方案数为 1)
[通过] n= 1, m= 3 -> 结果: 1 (1 阶台阶，只能走 1 步)
[通过] n= 2, m= 2 -> 结果: 2 (经典斐波那契走法: [1+1, 2])
[通过] n= 3, m= 2 -> 结果: 3 (经典斐波那契走法: [1+1+1, 1+2, 2+1])
[通过] n= 4, m= 4 -> 结果: 8 (m >= n 时，结果为 2^(4-1) = 8)
[通过] n= 5, m= 3 -> 结果: 13 (正文演算实例)
[通过] n=10, m= 1 -> 结果: 1 (m=1 时退化为唯一走法)
六、算法选型决策与知识总结
针对不同规模的 n 与 m，我们可以总结出清晰的算法选型策略：
综上所述，解决“每次走 1 至 m 阶”的通用爬楼梯问题，核心在于建立 dp[i] = ∑ dp[i-step] 的递推思维。理解从标准 O(n × m) 循环累加到 O(n) 滑动窗口维护前缀和的推导过程，能够帮助开发者在面对高并发、大数据量的状态转移计算时，写出兼具正确性与性能的通用 Python 解法。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
