2025-05-14：统计能获胜的出招序列数。用go语言，Alice 和 Bob 玩一个回合制幻想战斗游戏，游戏共进行 n 轮。

福大大架构师每日一题

发布于 2025-05-14 04:03:36

4800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-05-14：统计能获胜的出招序列数。用go语言，Alice 和 Bob 玩一个回合制幻想战斗游戏，游戏共进行 n 轮。每轮双方同时召唤一种魔法生物，三种生物分别是火龙（F）、水蛇（W）和地精（E）。

得分规则如下：

• 火龙击败地精，召唤火龙的一方得1分。
• 水蛇击败火龙，召唤水蛇的一方得1分。
• 地精击败水蛇，召唤地精的一方得1分。
• 如果双方召唤了相同的生物，则无分。

现在已知 Alice 每一轮召唤的生物序列 s（长度为 n，字符取自 {F, W, E}），但 Bob 的出招序列未知，只知道 Bob 不会连续两次召唤同样的生物。

问题是：满足 Bob 严格得分超过 Alice 的情况下，有多少种不同的 Bob 出招序列？由于结果可能非常大，需要对 1000000007 取模返回。

1 <= s.length <= 1000。

s[i] 是 'F'、'W' 或 'E' 中的一个。

输入： s = "FWEFW"。

输出： 18。

解释：

Bob 可以通过以下出招序列战胜：Alice："FWFWF"、"FWFWE"、"FWEFE"、"FWEWE"、"FEFWF"、"FEFWE"、"FEFEW"、"FEWFE"、"WFEFE"、"WFEWE"、"WEFWF"、"WEFWE"、"WEFEF"、"WEFEW"、"WEWFW"、"WEWFE"、"EWFWE" 或 "EWEWE"。

题目来自leetcode3320。

解决思路

动态规划状态定义

使用动态规划来解决这个问题。定义状态 f[i][j][pre]：

• i：已经处理了前 i 轮（从0到n）。
• j：当前Bob的净得分（Bob得分 - Alice得分），范围可能在 -n 到 n 之间。
• pre：Bob在前一轮出招的生物（0: F, 1: W, 2: E），用于确保当前轮不与前一轮相同。

初始化

• 初始状态 f[0][j][*] 表示处理了0轮时，净得分为 j 且前一轮出招为 * 的情况。由于没有出招，净得分需要初始化为一个合理的范围（代码中通过偏移 n 来处理负数）。
• 对于 j > i + 1 的情况，可以直接用 pow2（表示当前可能的序列数）填充，因为净得分已经足够大，后续无论如何出招都能满足严格大于的条件。

状态转移

对于每一轮 i 和当前字符 s[i]（Alice的出招）：

1. 遍历所有可能的净得分 j（从 -i 到 i）。
2. 遍历Bob前一轮的出招 pre（0, 1, 2）。
3. 对于当前轮，Bob可以选择不与 pre 相同的生物 cur（0, 1, 2且 cur != pre）。
4. 计算当前轮的得分贡献：
- • Bob出 cur，Alice出 mp[s[i]]（将字符映射为数字）。
- • 计算 score = (cur - mp[s[i]] + 3) % 3，根据得分规则调整：
  - • 如果 score == 2，表示Alice得分，score = -1。
  - • 如果 score == 1，表示Bob得分，score = 1。
  - • 如果 score == 0，表示平局，score = 0。
5. 更新净得分 j + score，并将状态转移到 f[i+1][j + score][cur]。

结果提取

最终答案是 f[n][k][*] 中 k > 0 的所有可能状态的和（即净得分严格大于0的情况）。

时间复杂度

• 外层循环：n 轮。
• 净得分范围：O(n)（从 -n 到 n，共 2n + 1 种）。
• 前一轮出招：3种。
• 当前轮出招：2种（不能与前一轮相同）。总时间复杂度为 O(n^2 * 3 * 2) = O(n^2)。

空间复杂度

• DP表 f 的大小为 (n+1) * (2n+1) * 3。
• 使用滚动数组可以优化空间，但最坏情况下仍然是 O(n^2)。

总结

• 时间复杂度：O(n^2)。
• 空间复杂度：O(n^2)。

Go完整代码如下：

package main

import (
    "fmt"
)

func countWinningSequences(s string)int {
    const mod = 1_000_000_007
    mp := [...]int{'F': 0, 'W': 1, 'E': 2}
    n := len(s)
    f := make([][][3]int, n+1)
    for i := range f {
        f[i] = make([][3]int, n*2+1)
    }
    for j := n + 1; j <= n*2; j++ {
        f[0][j] = [3]int{1, 1, 1}
    }
    pow2 := 1
    for i, c := range s {
        pow2 = pow2 * 2 % mod
        for j := -i; j < n-i; j++ {
            for pre := 0; pre < 3; pre++ {
                if j > i+1 {
                    f[i+1][j+n][pre] = pow2
                    continue
                }
                res := 0
                for cur := 0; cur < 3; cur++ {
                    if i == n-1 || cur != pre {
                        score := (cur - mp[c] + 3) % 3
                        if score == 2 {
                            score = -1
                        }
                        res += f[i][j+score+n][cur]
                    }
                }
                f[i+1][j+n][pre] = res % mod
            }
        }
    }
    return f[n][n][0]
}

func main() {
    s := "FWEFW"
    result := countWinningSequences(s)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defcountWinningSequences(s: str) -> int:
    mod = 10**9 + 7
    mp = {'F': 0, 'W': 1, 'E': 2}
    n = len(s)
    # f[i][j][pre]: 表示第 i 轮，当前得分差为 j - n（Bob得分- Alice得分），
    # Bob上一轮召唤的生物是 pre (0:F,1:W,2:E) 的方案数
    f = [[[0]*3for _ inrange(n*2+1)] for __ inrange(n+1)]

    # 初始化，得分差大于 n 时方案数为 1
    for j inrange(n+1, n*2+1):
        for pre inrange(3):
            f[0][j][pre] = 1

    pow2 = 1# 用于快速赋值
    for i, c inenumerate(s):
        pow2 = pow2 * 2 % mod
        for j inrange(-i, n - i):
            for pre inrange(3):
                if j > i + 1:
                    f[i+1][j+n][pre] = pow2
                    continue
                res = 0
                for cur inrange(3):
                    if i == n - 1or cur != pre:
                        score = (cur - mp[c] + 3) % 3
                        if score == 2:
                            score = -1
                        res += f[i][j + score + n][cur]
                f[i+1][j+n][pre] = res % mod

    return f[n][n][0]


if __name__ == "__main__":
    s = "FWEFW"
    result = countWinningSequences(s)
    print(result)