当前位置：首页 > news >正文

华为OD机试 - 超级玛丽通过吊桥的走法 - 动态规划（Python/JS/C/C++ 2024 E卷 200分）

news 来源：原创 2024/10/1 10:01:19

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

超级玛丽好不容易来到崭新的一关，有一个长长的吊桥，吊桥的尽头是下水管道，其中随机的木板存在缺失，且踩到就会死亡，死亡后如果还有剩余的生命将任然复活且不受木板缺失影响，但会消耗一次生命，如果跨过了管道，将踏入悬崖，通关失败。

超级玛丽从起点 S 处出发，可以走到下一个木板(计1)，也可以跳跃跨到下两个木板(计3)，最终必须刚好走到终点 D。现在给定超级玛丽当前的生命数 M，吊桥长度的木板数 N，缺失的木板数 K 以及随机缺失的木板编号数组 L, 请帮忙计算一下，超级玛丽有多少种方法可以通过此关。

二、输入描述

第一行三个整数，超级玛丽当前生命数 M(1<=M<=5), 吊桥的长度 N(1<=N<=32, 整数)，缺失木板数 K(K<=K<=32, 整数)
第二行为缺失木板编号数组 L:(长度为 K 的数组内容不大于 N 的编号数组), 1<=Li<=N，由空格分隔的整数数组。

三、输出描述

输出通过此关的吊桥走法个数，如果不能通过此关，请输出0。

提示：

输入总是合法，忽略参数较验
必须从起点开始
必须离开吊桥到到终点。

四、测试用例

1、输入

2 2 1
2

2、输出

3、说明

2个生命，2个木板，缺失1个木板，缺失1个木板，第2个木板有缺失，一共有4种走法

3
1 2
2 1
1（复活）1

五、解题思路

本题适合采用动态规划（Dynamic Programming, DP）的方法来解决。

动态规划：通过状态转移方程逐步计算每个状态下的走法数，最终汇总到达终点的所有有效走法。

本题需要考虑不同路径的组合，并且每一步的选择会影响后续的走法数，符合动态规划的典型应用场景。

具体步骤如下：

状态表示：
- 使用二维数组 dp[pos][lives] 表示到达位置 pos 时剩余生命数为 lives 的走法数。
状态转移：
- 步进：
  - 从 pos 到 pos + 1。
  - 如果 pos + 1 是缺失木板，消耗一次生命（前提是有剩余生命）。
- 跳跃：
  - 从 pos 到 pos + 2。
  - 如果 pos + 2 是缺失木板，消耗一次生命（前提是有剩余生命）。
初始化：
- 起点 S 对应的位置为0，初始生命数为 M，即 dp[0][M] = 1。
目标：
- 计算所有可能到达终点 D（位置 N + 1）的走法数。
边界条件：
- 必须刚好走到终点 D，不能超过。
- 如果没有足够的生命数来踩到缺失木板，则该路径不可行。

六、Python算法源码

# 导入所需的库
import sysdef main():# 读取输入的第一行，并将其拆分为整数 M, N, Kinput_line = sys.stdin.readline().strip()M, N, K = map(int, input_line.split())# 读取第二行，存储缺失木板的编号if K > 0:missing_planks = set(map(int, sys.stdin.readline().strip().split()))else:missing_planks = set()# 初始化动态规划数组，dp[pos][lives] 表示到达位置 pos 时剩余 lives 条生命的走法数dp = [[0] * (M + 1) for _ in range(N + 2)]dp[0][M] = 1  # 从起点开始，生命数为 M# 遍历每一个位置for pos in range(N + 1):for lives in range(M + 1):if dp[pos][lives] == 0:continue  # 如果当前状态没有走法，跳过# 尝试走一步到 pos + 1step1 = pos + 1if step1 <= N:if step1 in missing_planks:if lives > 0:dp[step1][lives - 1] += dp[pos][lives]  # 消耗一个生命else:dp[step1][lives] += dp[pos][lives]  # 不消耗生命elif step1 == N + 1:# 刚好走到终点，不需要消耗生命dp[step1][lives] += dp[pos][lives]# 尝试跳跃到 pos + 2step2 = pos + 2if step2 <= N:if step2 in missing_planks:if lives > 0:dp[step2][lives - 1] += dp[pos][lives]  # 消耗一个生命else:dp[step2][lives] += dp[pos][lives]  # 不消耗生命elif step2 == N + 1:# 刚好跳到终点，不需要消耗生命dp[step2][lives] += dp[pos][lives]# 计算所有到达终点的位置的走法数之和total_ways = sum(dp[N + 1])# 输出结果print(total_ways)# 调用主函数
if __name__ == "__main__":main()

七、JavaScript算法源码

// 引入readline模块以读取输入
const readline = require('readline');// 创建接口以读取标准输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let inputLines = [];
let currentLine = 0;// 读取所有输入行
rl.on('line', (line) => {inputLines.push(line);
});// 输入结束后执行的函数
rl.on('close', () => {// 读取第一行并解析 M, N, Klet firstLine = inputLines[0].trim().split(' ').map(Number);let M = firstLine[0]; // 生命数let N = firstLine[1]; // 木板数let K = firstLine[2]; // 缺失木板数// 读取缺失木板的编号并存入 Set 中let missingPlanks = new Set();if (K > 0) {let secondLine = inputLines[1].trim().split(' ').map(Number);for (let i = 0; i < K; i++) {missingPlanks.add(secondLine[i]);}}// 初始化动态规划数组，dp[pos][lives] 表示到达位置 pos 时剩余 lives 条生命的走法数let dp = Array.from({ length: N + 2 }, () => Array(M + 1).fill(0));dp[0][M] = 1; // 从起点开始，生命数为 M// 遍历每一个位置for (let pos = 0; pos <= N; pos++) {for (let lives = 0; lives <= M; lives++) {if (dp[pos][lives] === 0) continue; // 如果当前状态没有走法，跳过// 尝试走一步到 pos + 1let step1 = pos + 1;if (step1 <= N) {if (missingPlanks.has(step1)) {if (lives > 0) {dp[step1][lives - 1] += dp[pos][lives]; // 消耗一个生命}} else {dp[step1][lives] += dp[pos][lives]; // 不消耗生命}} else if (step1 === N + 1) {// 刚好走到终点，不需要消耗生命dp[step1][lives] += dp[pos][lives];}// 尝试跳跃到 pos + 2let step2 = pos + 2;if (step2 <= N) {if (missingPlanks.has(step2)) {if (lives > 0) {dp[step2][lives - 1] += dp[pos][lives]; // 消耗一个生命}} else {dp[step2][lives] += dp[pos][lives]; // 不消耗生命}} else if (step2 === N + 1) {// 刚好跳到终点，不需要消耗生命dp[step2][lives] += dp[pos][lives];}}}// 计算所有到达终点的位置的走法数之和let totalWays = 0;for (let lives = 0; lives <= M; lives++) {totalWays += dp[N + 1][lives];}// 输出结果console.log(totalWays);
});

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 最大木板数和生命数的限制
#define MAX_N 34
#define MAX_M 6int main() {int M, N, K;// 读取 M, N, Kscanf("%d %d %d", &M, &N, &K);// 创建一个数组标记缺失的木板int missingPlanks[MAX_N] = {0};for(int i = 0; i < K; i++) {int plank;scanf("%d", &plank);if(plank >=1 && plank <= N) {missingPlanks[plank] = 1; // 标记为缺失}}// 初始化动态规划数组，dp[pos][lives] 表示到达位置 pos 时剩余 lives 条生命的走法数long long dp[MAX_N][MAX_M];memset(dp, 0, sizeof(dp));dp[0][M] = 1; // 从起点开始，生命数为 M// 遍历每一个位置for(int pos = 0; pos <= N; pos++) {for(int lives = 0; lives <= M; lives++) {if(dp[pos][lives] == 0) continue; // 如果当前状态没有走法，跳过// 尝试走一步到 pos + 1int step1 = pos + 1;if(step1 <= N) {if(missingPlanks[step1]) {if(lives > 0) {dp[step1][lives -1] += dp[pos][lives]; // 消耗一个生命}}else {dp[step1][lives] += dp[pos][lives]; // 不消耗生命}}else if(step1 == N +1){// 刚好走到终点，不需要消耗生命dp[N+1][lives] += dp[pos][lives];}// 尝试跳跃到 pos + 2int step2 = pos + 2;if(step2 <= N) {if(missingPlanks[step2]) {if(lives > 0) {dp[step2][lives -1] += dp[pos][lives]; // 消耗一个生命}}else {dp[step2][lives] += dp[pos][lives]; // 不消耗生命}}else if(step2 == N +1){// 刚好跳到终点，不需要消耗生命dp[N+1][lives] += dp[pos][lives];}}}// 计算所有到达终点的位置的走法数之和long long totalWays = 0;for(int lives = 0; lives <= M; lives++) {totalWays += dp[N+1][lives];}// 输出结果printf("%lld\n", totalWays);return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;int main(){int M, N, K;// 读取 M, N, Kcin >> M >> N >> K;// 创建一个数组标记缺失的木板vector<int> missingPlanks(N+2, 0); // 1-based indexfor(int i = 0; i < K; i++) {int plank;cin >> plank;if(plank >=1 && plank <= N){missingPlanks[plank] = 1; // 标记为缺失}}// 初始化动态规划数组，dp[pos][lives] 表示到达位置 pos 时剩余 lives 条生命的走法数// 使用 long long 防止大数vector<vector<long long>> dp(N+2, vector<long long>(M+1, 0));dp[0][M] = 1; // 从起点开始，生命数为 M// 遍历每一个位置for(int pos = 0; pos <= N; pos++) {for(int lives = 0; lives <= M; lives++) {if(dp[pos][lives] == 0) continue; // 如果当前状态没有走法，跳过// 尝试走一步到 pos + 1int step1 = pos + 1;if(step1 <= N){if(missingPlanks[step1]){if(lives > 0){dp[step1][lives -1] += dp[pos][lives]; // 消耗一个生命}}else{dp[step1][lives] += dp[pos][lives]; // 不消耗生命}}else if(step1 == N +1){// 刚好走到终点，不需要消耗生命dp[N+1][lives] += dp[pos][lives];}// 尝试跳跃到 pos + 2int step2 = pos + 2;if(step2 <= N){if(missingPlanks[step2]){if(lives > 0){dp[step2][lives -1] += dp[pos][lives]; // 消耗一个生命}}else{dp[step2][lives] += dp[pos][lives]; // 不消耗生命}}else if(step2 == N +1){// 刚好跳到终点，不需要消耗生命dp[N+1][lives] += dp[pos][lives];}}}// 计算所有到达终点的位置的走法数之和long long totalWays = 0;for(int lives = 0; lives <= M; lives++){totalWays += dp[N+1][lives];}// 输出结果cout << totalWays << endl;return 0;
}