【DP】2023Q1A-猴子爬山
题目描述与示例
题目
一天一只顽猴想要从山脚爬到山顶，途中经过一个有 n 个台阶的阶梯，但是这个猴子有个习惯，每一次只跳 1 步或 3 步。试问猴子通过这个阶梯有多少种不同的跳跃方式。
输入
输入只有一个数 n， 0 <= n <= 50，代表此阶梯有多个台阶。
输出描述
一个整数，表示有多少种跳跃方式。
示例一
输入
50
输出
122106097
示例二
输入
3
输出
2
解题思路
注意：本题和 LC70. 爬楼梯几乎完全一致。唯一区别在于，猴子更加调皮，每次是跳 1 或 3 个台阶，而不是 1 或 2 个台阶。
这是一个典型的 dp 问题。我们考虑动态规划三部曲：
-
dp 数组的含义是什么？
-
dp 数组是一个长度为 n+1 的一维列表，dp[i] 表示猴子到达第 i 个台阶一共有多少种跳跃方式。
- 动态转移方程是什么？
- 跳跃到第
i 个台阶的方法数 dp[i]，等于到达其前一个台阶的方法数 dp[i-1]，加上到达其前三个台阶的方法数 dp[i-3] 之和。即存在
dp[i] = dp[i-1] + dp[i-3]
-
dp 数组如何初始化？
- 第
0 个台阶，即起点位置，猴子只有 1 种方法能够到达
- 第
1 个台阶，猴子只能从起点位置跳上来，只有 1 种方法能够到达
- 第
2 个台阶，猴子只能从第 1 个台阶跳上来，只有 1 种方法能够到达
# 第0，1，2个台阶均只有1种跳跃方式到达
dp[0] = 1
dp[1] = 1
dp[2] = 1
考虑完上述问题后，代码其实呼之欲出了。
代码
# 题目：2023Q1A-猴子爬山
# 分值：100
# 作者：许老师：闭着眼睛学数理化
# 算法：动态规划（序列dp）
# 代码看不懂的地方，请直接在群上提问
n = int(input())
# 初始化dp数组
# dp[i]表示到达第i个台阶一共有多少种跳跃方式
dp = [0] * (n+1)
# 第0，1，2个台阶均只有1种跳跃方式到达
dp[0] = 1
dp[1] = 1
dp[2] = 1
# 从第3个台阶开始，遍历剩余的所有台阶i，
# 跳跃到每一个台阶的方法数，
# 等于到达其前一个台阶的方法数dp[i-1]
# 加上到达其前三个台阶的方法数dp[i-3]之和
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-3]
# 输出第n个台阶的方法数
print(dp[n])
时空复杂度
时间复杂度：O(N)。对每一个台阶都要计算到达该台阶的方法数。
空间复杂度：O(N)。dp 数组所占据的空间。
华为OD算法冲刺训练
-
华为OD算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
-
30+天陪伴式学习，20+直播课时，300+动画图解视频，200+LeetCode经典题，100+华为OD真题，还有简历修改与模拟面试将为你解锁
-
可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)
-
绿色聊天软件戳 sheepvipvip了解更多
