华为OD统一考试 - 抢7游戏

题目描述

A、B两个人玩抢7游戏,游戏规则为:

A先报一个起始数字 X(10 ≤ 起始数字 ≤ 10000),B报下一个数字 Y (X - Y < 3),A再报一个数字 Z(Y - Z < 3),以此类推,直到其中一个抢到7,抢到7即为胜者;

在B赢得比赛的情况下,一共有多少种组合?

输入描述

起始数字 M

  • 10 ≤ M ≤ 10000

如:

100

输出描述

B能赢得比赛的组合次数

用例

输入

10

输出

1

说明

数学分析解法(可能会超时)

下面模拟M为10~14时,B能够获胜的一些情况:

本题最优解法为动态规划,动态规划的逻辑很简单,假设A从m开始叫,那么:

B叫了数字 i 的方案数有多少种呢?

如果B叫了数字 i,那么上一把A可能会叫数字i+1,也可能叫数字i+2

dpB[i] 表示 B 能叫到数字 i 的方案数

dpA[i] 表示 A 能叫到数字 j 的方案数

那么 dpB[i] = dpA[i+1] + dpA[i+2]

同理的是,如果A叫了数字 i,那么上一把B可能会叫数字i+1,也可能会叫数字 i+2

那么 dpA[i] = dpB[i+1] + dpB[i+2]

初始时,是A从m开始叫,因此 dpA[m] = 1,即A叫到数字m的方案数为1。而B肯定叫不到数字m,因此初始化dpB[m] = 0。

之后我们可以递推出dpB[m-1],即B叫出数字m-1的方案数,即dpB[m-1] = dpA[m] + dp[m+1]

提示,根据dpB[m-1] = dpA[m] + dpA[m+1]的递推式,我们可以了解到dpA,dpB数组的长度应该初始化为m+2,这样上面递推式才不会越界。

且dpA[m] = 1,dpA[m+1]

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024华为OD机试卷题 文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。

全部评论

相关推荐

昨天 15:45
辽宁大学 golang
咱就是说&nbsp;你不主动&nbsp;我也不会主动下一步hhh,急死了
恶龙战士:不建议把这种帖子发到牛客上,建议去小红书发
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-10 15:24
高考前一晚在OPPO手机上设置了早上5:30的闹钟,然而闹钟并未按时响起。直到妈妈做好早餐后,在6:27打开手机才发现闹钟未触发,“气得早上饭都没吃”。资本家你赢了
永不遗忘:我来解释一下 :Oppo 手机晚上两点会自动进行系统更新,这个系统更新会重置掉所有设置好的闹钟,而且他也不会告诉你,而且只有 Oppo 会这样,华为苹果小米三星都不会
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务