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-*-

def countWinningSequences(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]*3 for _ in range(n*2+1)] for __ in range(n+1)]

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

    pow2 = 1  # 用于快速赋值
    for i, c in enumerate(s):
        pow2 = pow2 * 2 % mod
        for j in range(-i, n - i):
            for pre in range(3):
                if j > i + 1:
                    f[i+1][j+n][pre] = pow2
                    continue
                res = 0
                for cur in range(3):
                    if i == n - 1 or 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)