华为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能赢得比赛的组合次数

用例

数学分析解法（可能会超时）

下面模拟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] = 0

而数字m-1，对于A而言是叫不到的，因此dpA[m-1]=0，但是也可以基于递推式得到：

dpA[m-1] = dpB[m] + dpB[m+1]，而dpB[m]和dpB[m+1]都应该初始化为0。

因此我们只需要按照上面递推式，一直递推到dpB[7]即可返回。

import Foundation

func ODTest_2_23() {
    print("输入描述")
    print("起始数字 M， 10 ≤ M ≤ 10000")
    let M = Int(readLine() ?? "") ?? 0
    print("输出描述")
    print("B能赢得比赛的组合次数")
    if M < 10 || M > 10000 {
        print("-1")
        return
    }

    // dpA[i] 表示 A 叫 数字i 的方案数
    var dpA: [Int64] = Array(repeating: 0, count: M + 2)
    // 初始化dpA[i]
    for i in 0 ..< M + 2 {
        dpA[i] = 0
    }
    // 由于是A从m开始叫，因此A叫m的方案数为1
    dpA[M] = 1

    // dpB[i] 表示 B叫 数字i 的方案数
    var dpB: [Int64] = Array(repeating: 0, count: M + 2)
    // 初始化dpB[i]
    for i in 0 ..< M + 2 {
        dpB[i] = 0
    }
    for i in stride(from: M - 1, to: 6, by: -1) {
        // B叫数字i的方案数 = A叫数字i+1的方案数 + A叫数字i+2的方案数
        dpB[i] = dpA[i + 1] + dpA[i + 2]
        // A叫数字i的方案数 = B叫数字i+1的方案数 + B叫数字i+2的方案数
        dpA[i] = dpB[i + 1] + dpB[i + 2]
    }
    // 返回B叫7的方案数
    print("\(dpB[7])")
}