class Solution {
public:
int countWinningSequences(string s) {
}
};
3320. 统计能获胜的出招序列数
Alice 和 Bob 正在玩一个幻想战斗游戏，游戏共有 n 回合，每回合双方各自都会召唤一个魔法生物：火龙（F）、水蛇（W）或地精（E）。每回合中，双方 同时 召唤魔法生物，并根据以下规则得分：
给你一个字符串 s，包含 n 个字符 'F'、'W' 和 'E'，代表 Alice 每回合召唤的生物序列：
s[i] == 'F'，Alice 召唤火龙。s[i] == 'W'，Alice 召唤水蛇。s[i] == 'E'，Alice 召唤地精。Bob 的出招序列未知，但保证 Bob 不会在连续两个回合中召唤相同的生物。如果在 n 轮后 Bob 获得的总分 严格大于 Alice 的总分，则 Bob 战胜 Alice。
返回 Bob 可以用来战胜 Alice 的不同出招序列的数量。
由于答案可能非常大，请返回答案对 109 + 7 取余 后的结果。
示例 1：
输入： s = "FFF"
输出： 3
解释：
Bob 可以通过以下 3 种出招序列战胜 Alice："WFW"、"FWF" 或 "WEW"。注意，其他如 "WWE" 或 "EWW" 的出招序列是无效的，因为 Bob 不能在连续两个回合中使用相同的生物。
示例 2：
输入： s = "FWEFW"
输出： 18
解释：
Bob 可以通过以下出招序列战胜 Alice："FWFWF"、"FWFWE"、"FWEFE"、"FWEWE"、"FEFWF"、"FEFWE"、"FEFEW"、"FEWFE"、"WFEFE"、"WFEWE"、"WEFWF"、"WEFWE"、"WEFEF"、"WEFEW"、"WEWFW"、"WEWFE"、"EWFWE" 或 "EWEWE"。
提示：
1 <= s.length <= 1000s[i] 是 'F'、'W' 或 'E' 中的一个。相似题目
原站题解
golang 解法, 执行用时: 127 ms, 内存消耗: 60.6 MB, 提交时间: 2024-10-19 14:12:33
func countWinningSequences(s string) int {
const mod = 1_000_000_007
n := len(s)
pow2 := make([]int, (n+1)/2)
pow2[0] = 1
for i := 1; i < len(pow2); i++ {
pow2[i] = pow2[i-1] * 2 % mod
}
mp := [...]int{'F': 0, 'W': 1, 'E': 2}
memo := make([][][3]int, n)
for i := range memo {
memo[i] = make([][3]int, n*2+1)
for j := range memo[i] {
memo[i][j] = [3]int{-1, -1, -1} // -1 表示没有计算过
}
}
var dfs func(int, int, int) int
dfs = func(i, j, ban int) (res int) {
if -j > i { // 必败
return
}
if j > i+1 { // 必胜
return pow2[i+1]
}
p := &memo[i][j+n][ban]
if *p != -1 { // 之前计算过
return *p
}
for k := 0; k < 3; k++ { // 枚举当前召唤的生物
// 判断 i == n-1，避免讨论 k == ban 的情况
if i == n-1 || k != ban { // 不能连续两个回合召唤相同的生物
score := (k - mp[s[i]] + 3) % 3
if score == 2 {
score = -1
}
res += dfs(i-1, j+score, k)
}
}
res %= mod
*p = res // 记忆化
return
}
return dfs(n-1, 0, 0) // ban=0,1,2 都可以
}
func countWinningSequences2(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]
}
python3 解法, 执行用时: 5779 ms, 内存消耗: 273.1 MB, 提交时间: 2024-10-19 14:12:04
class Solution:
def countWinningSequences(self, s: str) -> int:
MOD = 1_000_000_007
n = len(s)
f = [[[0] * 3 for _ in range(n * 2 + 1)] for _ in range(n + 1)]
for j in range(n + 1, n * 2 + 1):
f[0][j] = [1] * 3
mp = {'F': 0, 'W': 1, 'E': 2}
pow2 = 1
for i, c in enumerate(s):
x = mp[c]
pow2 = pow2 * 2 % MOD
for j in range(-i, n - i):
for ban in range(3):
if j > i + 1:
f[i + 1][j + n][ban] = pow2
continue
res = 0
for k in range(3):
if i == n - 1 or k != ban:
score = (k - x) % 3
if score == 2:
score = -1
res += f[i][j + score + n][k]
f[i + 1][j + n][ban] = res % MOD
return f[n][n][0]
def countWinningSequences2(self, s: str) -> int:
MOD = 1_000_000_007
mp = {c: i for i, c in enumerate("FWE")}
s = [mp[c] for c in s]
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int, ban: int) -> int:
if -j > i: # 必败
return 0
if j > i + 1: # 必胜
return pow(2, i + 1, MOD)
res = 0
for k in range(3): # 枚举当前召唤的生物
if k == ban: # 不能连续两个回合召唤相同的生物
continue
score = (k - s[i]) % 3
if score == 2:
score = -1
res += dfs(i - 1, j + score, k)
return res % MOD
return dfs(len(s) - 1, 0, -1)
cpp 解法, 执行用时: 215 ms, 内存消耗: 106.1 MB, 提交时间: 2024-10-19 14:11:31
class Solution {
public:
int countWinningSequences(string s) {
const int MOD = 1'000'000'007;
int mp[128];
mp['F'] = 0;
mp['W'] = 1;
mp['E'] = 2;
int n = s.length();
vector<int> pow2((n + 1) / 2);
pow2[0] = 1;
for (int i = 1; i < pow2.size(); i++) {
pow2[i] = pow2[i - 1] * 2 % MOD;
}
vector<vector<array<int, 3>>> memo(n, vector<array<int, 3>>(n * 2 + 1, {-1, -1, -1}));
auto dfs = [&](auto&& dfs, int i, int j, int ban) -> int {
if (-j > i) { // 必败
return 0;
}
if (j > i + 1) { // 必胜
return pow2[i + 1];
}
int& res = memo[i][j + n][ban]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
res = 0;
for (int k = 0; k < 3; k++) { // 枚举当前召唤的生物
// 判断 i == n - 1，避免讨论 k == ban 的情况
if (i == n - 1 || k != ban) { // 不能连续两个回合召唤相同的生物
int score = (k - mp[s[i]] + 3) % 3;
if (score == 2) {
score = -1;
}
res = (res + dfs(dfs, i - 1, j + score, k)) % MOD;
}
}
return res;
};
return dfs(dfs, n - 1, 0, 0); // ban=0,1,2 都可以
}
int countWinningSequences2(string s) {
const int MOD = 1'000'000'007;
int mp[128];
mp['F'] = 0;
mp['W'] = 1;
mp['E'] = 2;
int n = s.size();
vector<vector<array<int, 3>>> f(n + 1, vector<array<int, 3>>(n * 2 + 1));
for (int j = n + 1; j <= n * 2; j++) {
f[0][j] = {1, 1, 1};
}
int pow2 = 1;
for (int i = 0; i < n; i++) {
int x = mp[s[i]];
pow2 = pow2 * 2 % MOD;
for (int j = -i; j < n - i; j++) {
for (int ban = 0; ban < 3; ban++) {
if (j > i + 1) {
f[i + 1][j + n][ban] = pow2;
continue;
}
int& res = f[i + 1][j + n][ban]; // 注意这里是引用
for (int k = 0; k < 3; k++) {
if (i == n - 1 || k != ban) {
int score = (k - x + 3) % 3;
if (score == 2) {
score = -1;
}
res = (res + f[i][j + score + n][k]) % MOD;
}
}
}
}
}
return f[n][n][0];
}
};
java 解法, 执行用时: 313 ms, 内存消耗: 178.1 MB, 提交时间: 2024-10-19 14:10:39
class Solution {
private static final int MOD = 1_000_000_007;
private static final int[] MAP = new int[128];
static {
MAP['F'] = 0;
MAP['W'] = 1;
MAP['E'] = 2;
}
public int countWinningSequences(String S) {
char[] s = S.toCharArray();
int n = s.length;
int[][][] f = new int[n + 1][n * 2 + 1][3];
for (int j = n + 1; j <= n * 2; j++) {
Arrays.fill(f[0][j], 1);
}
int pow2 = 1;
for (int i = 0; i < n; i++) {
int x = MAP[s[i]];
pow2 = pow2 * 2 % MOD;
for (int j = -i; j < n - i; j++) {
for (int ban = 0; ban < 3; ban++) {
if (j > i + 1) {
f[i + 1][j + n][ban] = pow2;
continue;
}
int res = 0;
for (int k = 0; k < 3; k++) {
if (i == n - 1 || k != ban) {
int score = (k - x + 3) % 3;
if (score == 2) {
score = -1;
}
res = (res + f[i][j + score + n][k]) % MOD;
}
}
f[i + 1][j + n][ban] = res;
}
}
}
return f[n][n][0];
}
}
java 解法, 执行用时: 347 ms, 内存消耗: 183.3 MB, 提交时间: 2024-10-19 14:10:24
class Solution {
private static final int MOD = 1_000_000_007;
private static final int[] MAP = new int[128];
private static final int[] POW2 = new int[500];
static {
MAP['F'] = 0;
MAP['W'] = 1;
MAP['E'] = 2;
POW2[0] = 1;
for (int i = 1; i < POW2.length; i++) {
POW2[i] = POW2[i - 1] * 2 % MOD;
}
}
public int countWinningSequences(String s) {
int n = s.length();
int[][][] memo = new int[n][n * 2 + 1][3];
for (int[][] mat : memo) {
for (int[] row : mat) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
}
return dfs(n - 1, 0, 0, s.toCharArray(), memo);
}
private int dfs(int i, int j, int ban, char[] s, int[][][] memo) {
if (-j > i) { // 必败
return 0;
}
if (j > i + 1) { // 必胜
return POW2[i + 1];
}
int n = s.length;
if (memo[i][j + n][ban] != -1) { // 之前计算过
return memo[i][j + n][ban];
}
int res = 0;
for (int k = 0; k < 3; k++) { // 枚举当前召唤的生物
// 判断 i == n - 1，避免讨论 k == ban 的情况
if (i == n - 1 || k != ban) { // 不能连续两个回合召唤相同的生物
int score = (k - MAP[s[i]] + 3) % 3;
if (score == 2) {
score = -1;
}
res = (res + dfs(i - 1, j + score, k, s, memo)) % MOD;
}
}
return memo[i][j + n][ban] = res; // 记忆化
}
}