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

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

article 2024/11/19 19:16:48

在这里插入图片描述

华为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. 必须从起点开始
  3. 必须离开吊桥到到终点。

四、测试用例

1、输入

2 2 1
2

2、输出

4

3、说明

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

3
1 2
2 1
1（复活）1

五、解题思路

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

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

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

具体步骤如下：

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

六、Python算法源码

# 导入所需的库
import sys

def main():
    # 读取输入的第一行，并将其拆分为整数 M, N, K
    input_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 + 1
            step1 = pos + 1
            if 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 + 2
            step2 = pos + 2
            if 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, K
    let 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 + 1
            let 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 + 2
            let 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 6

int main() {
    int M, N, K;
    
    // 读取 M, N, K
    scanf("%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 + 1
            int 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 + 2
            int 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, K
    cin >> M >> N >> K;
    
    // 创建一个数组标记缺失的木板
    vector<int> missingPlanks(N+2, 0); // 1-based index
    for(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 + 1
            int 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 + 2
            int 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;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

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

在这里插入图片描述


http://www.kler.cn/a/327314.html

相关文章：

  • 如何在 Ubuntu 上安装 Jupyter Notebook
  • [前端面试]HTML AND CSS
  • 基于多模板配准的心腔分割算法
  • SpringBoot源码解析(四)：解析应用参数args
  • 【汇编语言】数据处理的两个基本问题（二） —— 解密汇编语言：数据长度与寻址方式的综合应用
  • Http常⻅见请求/响应头content-type内容类型讲解（笔记）
  • 数据结构——计数、桶、基数排序
  • 深入探索 PyTorch 在机器学习中的应用
  • 观测云对接 SkyWalking 最佳实践
  • Springboot中yml文件不生效原因分析及解决
  • 【C++篇】启航——初识C++（下篇）
  • 滚雪球学Oracle[7.1讲]：Oracle云数据库
  • 如何从 Windows 11/10/8.1/8/7 中恢复已删除的视频
  • 前端导出页面PDF
  • rust的nutyp验证和validator验证数据的方法
  • MySQL | group by 用法
  • 牛客周赛 Round 62
  • 828华为云征文｜部署个人文档管理系统 Docspell
  • Kali Linux安全工具
  • 实战OpenCV之形态学操作
  • 网络带宽对于服务器的影响
  • 云原生之运维监控实践-使用Prometheus与Grafana实现对MySQL和Redis服务的监测
  • Drf认证组件
  • Feign 主要负责简化 HTTP API 的调用逻辑； Eureka 负责服务实例的注册和服务发现； Ribbon 则负责实现客户端的负载均衡。
  • UE4_Niagara基础实例—7、如何让粒子照亮周边环境
  • 制造企业各部门如何参与生产成本控制与管理？