2025A-猴子爬山
题目描述与示例
题目
一天一只顽猴想要从山脚爬到山顶，途中经过一个有 n 个台阶的阶梯，但是这个猴子有个习惯，每一次只跳 1 步或 3 步。试问猴子通过这个阶梯有多少种不同的跳跃方式。
题目练习网址：https://www.algomooc.com/problem/P3399
输入
输入只有一个数 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考虑完上述问题后，代码其实呼之欲出了。
代码
Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频
n = int(input())
if n <= 2:
print(1)
else:
# 初始化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])Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
if (n <= 2) {
System.out.println(1);
} else {
// 初始化dp数组
// dp[i]表示到达第i个台阶一共有多少种跳跃方式
int[] dp = new int[n+1];
// 第0，1，2个台阶均只有1种跳跃方式到达
dp[0] = 1;
dp[1] = 1;
dp[2] = 1;
// 从第3个台阶开始，遍历剩余的所有台阶i，
// 跳跃到每一个台阶的方法数，
// 等于到达其前一个台阶的方法数dp[i-1]
// 加上到达其前三个台阶的方法数dp[i-3]之和
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-3];
}
// 输出第n个台阶的方法数
System.out.println(dp[n]);
}
}
}C++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
if (n <= 2) {
cout << 1 << endl;
} else {
// 初始化dp数组
// dp[i]表示到达第i个台阶一共有多少种跳跃方式
vector<int> dp(n+1);
// 第0，1，2个台阶均只有1种跳跃方式到达
dp[0] = 1;
dp[1] = 1;
dp[2] = 1;
// 从第3个台阶开始，遍历剩余的所有台阶i，
// 跳跃到每一个台阶的方法数，
// 等于到达其前一个台阶的方法数dp[i-1]
// 加上到达其前三个台阶的方法数dp[i-3]之和
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-3];
}
// 输出第n个台阶的方法数
cout << dp[n] << endl;
}
return 0;
}C
#include <stdio.h>
#include <stdlib.h>
int main() {
int n;
scanf("%d", &n);
if (n <= 2) {
// 如果台阶数小于等于2，跳法只有1种
printf("1\n");
} else {
// 初始化dp数组
// dp[i] 表示到达第 i 个台阶一共有多少种跳跃方式
int* dp = (int*)malloc((n + 1) * sizeof(int));
// 第 0，1，2 个台阶均只有 1 种跳跃方式到达
dp[0] = 1;
dp[1] = 1;
dp[2] = 1;
// 从第 3 个台阶开始，遍历剩余的所有台阶 i，
// 跳跃到每一个台阶的方法数，
// 等于到达其前一个台阶的方法数 dp[i-1]
// 加上到达其前三个台阶的方法数 dp[i-3] 之和
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
// 输出第 n 个台阶的方法数
printf("%d\n", dp[n]);
// 释放动态分配的内存
free(dp);
}
return 0;
}Node JavaScript
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.on("line", function (line) {
const n = parseInt(line);
if (n <= 2) {
console.log(1);
} else {
// 初始化dp数组
// dp[i] 表示到达第 i 个台阶一共有多少种跳跃方式
const dp = new Array(n + 1).fill(0);
// 第 0, 1, 2 个台阶均只有 1 种跳跃方式到达
dp[0] = 1;
dp[1] = 1;
dp[2] = 1;
// 从第 3 个台阶开始，遍历剩余的所有台阶 i，
// 跳跃到每一个台阶的方法数，
// 等于到达其前一个台阶的方法数 dp[i-1]
// 加上到达其前三个台阶的方法数 dp[i-3] 之和
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
// 输出第 n 个台阶的方法数
console.log(dp[n]);
}
rl.close();
});Go
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
// 从标准输入读取一个整数
reader := bufio.NewReader(os.Stdin)
input, _ := reader.ReadString('\n')
input = strings.TrimSpace(input)
n, _ := strconv.Atoi(input)
if n <= 2 {
fmt.Println(1)
} else {
// 初始化dp数组
// dp[i] 表示到达第 i 个台阶一共有多少种跳跃方式
dp := make([]int, 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 := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-3]
}
// 输出第 n 个台阶的方法数
fmt.Println(dp[n])
}
}时空复杂度
时间复杂度：O(N)。对每一个台阶都要计算到达该台阶的方法数。
空间复杂度：O(N)。dp数组所占据的空间。