P3399. 猴子爬山

解题思路

题目说明

注意：本题和 爬楼梯 几乎完全一致。唯一区别在于，猴子更加调皮，每次是跳 1 或 3 个台阶，而不是 1 或 2 个台阶。

动态规划三部曲

1. dp 数组的含义是什么？

dp 数组 是一个长度为 n+1 的一维列表，dp[i] 表示猴子到达第 i 个台阶一共有多少种跳跃方式。

2. 动态转移方程是什么？

跳跃到第 i 个台阶的方法数 dp[i]，等于到达其前一个台阶的方法数 dp[i-1]，加上到达其前三个台阶的方法数 dp[i-3] 之和。即存在：

3. dp 数组如何初始化？

• 第 0 个台阶，即起点位置，猴子只有 1 种方法 能够到达
• 第 1 个台阶，猴子只能从起点位置跳上来，只有 1 种方法 能够到达
• 第 2 个台阶，猴子只能从第 1 个台阶跳上来，只有 1 种方法 能够到达

关键结论：第 0、1、2 个台阶均只有 1 种跳跃方式 到达。

考虑完上述问题后，代码其实呼之欲出了。

思路展开 把走台阶的方案按最后一步分类：小慕到达第 i 级台阶时，最后一步要么是从第 i-1 级跳 1 步上来，要么是从第 i-3 级跳 3 步上来，这两类方案互不重叠也不遗漏，所以 dp[i] = dp[i-1] + dp[i-3]。dp 数组长度为 n+1，dp[i] 表示到达第 i 级台阶的方案总数。起点 dp[0] = 1 表示还没起跳时算一种基础状态；第 1、2 级台阶只能靠连续跳 1 步到达，各只有一种走法，所以 dp[1] = dp[2] = 1。主循环从 i = 3 开始逐级向后推，每个 dp[i] 只依赖前面已经算好的 dp[i-1] 和 dp[i-3]，最后输出 dp[n] 即为答案。 复杂度分析 设 n 为台阶总数。

• 时间复杂度：O(n)。只有一个从 3 到 n 的单层循环，每步做一次加法。
• 空间复杂度：O(n)，用于长度 n+1 的 dp 数组。由于每一步只用到 dp[i-1] 与 dp[i-3]，也可以只保留最近 3 个值把空间降到 O(1)，代码为了直观保留了完整数组。

边界与注意事项

• n 不超过 2 时代码直接输出 1，不进入 dp 流程：一方面此时只能一路跳 1 步、答案确实是 1；另一方面若不特判，n = 1 时给 dp[2] 赋初值会越界（数组长度只有 2）。
• 方案数随 n 呈指数级增长（每一项都是前面两项之和的量级）。Python 的整数不会溢出；C++ 版本用 int 存储，若数据中 n 较大需留意乘积溢出问题，可换用 long long。