3320. 计算获胜序列的数量

Hard

题目描述

Alice 和 Bob 在玩一个由 n 轮组成的幻想战斗游戏，每轮他们都会召唤三种魔法生物中的一种：火龙、水蛇或土巨人。在每一轮中，玩家同时召唤他们的生物并按照以下规则获得分数：

如果一个玩家召唤火龙而另一个召唤土巨人，召唤火龙的玩家获得一分。
如果一个玩家召唤水蛇而另一个召唤火龙，召唤水蛇的玩家获得一分。
如果一个玩家召唤土巨人而另一个召唤水蛇，召唤土巨人的玩家获得一分。
如果两个玩家召唤相同的生物，没有玩家获得分数。

给你一个由 n 个字符 ‘F’、‘W’ 和 ‘E’ 组成的字符串 s，表示 Alice 在每轮中召唤的生物序列：

如果 s[i] == ‘F’，Alice 召唤火龙。
如果 s[i] == ‘W’，Alice 召唤水蛇。
如果 s[i] == ‘E’，Alice 召唤土巨人。

Bob 的移动序列是未知的，但保证 Bob 永远不会在连续两轮中召唤相同的生物。如果 Bob 在 n 轮后获得的总分数严格大于 Alice 获得的分数，则 Bob 击败 Alice。

返回 Bob 可以用来击败 Alice 的不同序列的数量。

由于答案可能非常大，请返回模 10^9 + 7 的结果。

示例 1：

输入：s = "FFF"
输出：3
解释：Bob 可以通过以下序列之一击败 Alice："WFW"、"FWF" 或 "WEW"。注意其他获胜序列如 "WWE" 或 "EWW" 是无效的，因为 Bob 不能连续两次做相同的移动。

示例 2：

输入：s = "FWEFW"
输出：18

约束条件：

1 <= s.length <= 1000
s[i] 是 ‘F’、‘W’ 或 ‘E’ 中的一个。

解题思路

这是一个经典的动态规划问题。我们需要考虑三个维度的状态：

当前回合数：从 0 到 n-1
分数差：Bob 的分数减去 Alice 的分数，范围是 [-n, n]
Bob 上一次的选择：‘F’、‘W’ 或 ‘E’

状态定义： dp[i][j][k] 表示在第 i 轮结束后，分数差为 j，Bob 在第 i 轮选择 k 的方案数。

状态转移： 对于每一轮，我们枚举 Bob 可能的选择（不能与上一轮相同），然后根据游戏规则计算分数变化：

火龙 vs 土巨人：火龙获胜 (+1 分)
水蛇 vs 火龙：水蛇获胜 (+1 分)
土巨人 vs 水蛇：土巨人获胜 (+1 分)
相同生物：平局 (0 分)

优化技巧： 为了处理负数索引，我们将分数差偏移 n，使其范围变为 [0, 2n]。

最终答案： 统计所有分数差大于 0 的状态数量之和。

时间复杂度 O(n²)，空间复杂度 O(n²)。

代码实现

class Solution {
public:
    int countWinningSequences(string s) {
        const int MOD = 1e9 + 7;
        int n = s.size();
        
        // dp[i][j][k] = number of ways at round i, score diff j+n, last move k
        vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(2*n+1, vector<long long>(3, 0)));
        
        auto getScore = [](char alice, char bob) -> int {
            if (alice == bob) return 0;
            if (alice == 'F' && bob == 'W') return 1;
            if (alice == 'W' && bob == 'E') return 1;
            if (alice == 'E' && bob == 'F') return 1;
            return -1;
        };
        
        auto charToInt = [](char c) -> int {
            if (c == 'F') return 0;
            if (c == 'W') return 1;
            return 2;
        };
        
        // Initialize first round
        for (int k = 0; k < 3; k++) {
            char bobMove = (k == 0) ? 'F' : (k == 1) ? 'W' : 'E';
            int score = getScore(s[0], bobMove);
            dp[0][score + n][k] = 1;
        }
        
        // Fill DP table
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                for (int prevK = 0; prevK < 3; prevK++) {
                    if (dp[i-1][j][prevK] == 0) continue;
                    
                    for (int k = 0; k < 3; k++) {
                        if (k == prevK) continue; // Can't use same move consecutively
                        
                        char bobMove = (k == 0) ? 'F' : (k == 1) ? 'W' : 'E';
                        int score = getScore(s[i], bobMove);
                        int newJ = j + score;
                        
                        if (newJ >= 0 && newJ <= 2*n) {
                            dp[i][newJ][k] = (dp[i][newJ][k] + dp[i-1][j][prevK]) % MOD;
                        }
                    }
                }
            }
        }
        
        // Sum all winning states (score > 0)
        long long result = 0;
        for (int j = n + 1; j <= 2*n; j++) {
            for (int k = 0; k < 3; k++) {
                result = (result + dp[n-1][j][k]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def countWinningSequences(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)
        
        def get_score(alice, bob):
            if alice == bob:
                return 0
            if (alice, bob) in [('F', 'W'), ('W', 'E'), ('E', 'F')]:
                return 1
            return -1
        
        # dp[i][j][k] = ways at round i, score diff j+n, last move k
        dp = [[[0] * 3 for _ in range(2*n+1)] for _ in range(n)]
        
        # Initialize first round
        moves = ['F', 'W', 'E']
        for k in range(3):
            score = get_score(s[0], moves[k])
            dp[0][score + n][k] = 1
        
        # Fill DP table
        for i in range(1, n):
            for j in range(2*n+1):
                for prev_k in range(3):
                    if dp[i-1][j][prev_k] == 0:
                        continue
                    
                    for k in range(3):
                        if k == prev_k:  # Can't use same move consecutively
                            continue
                        
                        score = get_score(s[i], moves[k])
                        new_j = j + score
                        
                        if 0 <= new_j <= 2*n:
                            dp[i][new_j][k] = (dp[i][new_j][k] + dp[i-1][j][prev_k]) % MOD
        
        # Sum all winning states (score > 0)
        result = 0
        for j in range(n + 1, 2*n + 1):
            for k in range(3):
                result = (result + dp[n-1][j][k]) % MOD
        
        return result

public class Solution {
    public int CountWinningSequences(string s) {
        const int MOD = 1000000007;
        int n = s.Length;
        
        int GetScore(char alice, char bob) {
            if (alice == bob) return 0;
            if ((alice == 'F' && bob == 'W') || 
                (alice == 'W' && bob == 'E') || 
                (alice == 'E' && bob == 'F')) return 1;
            return -1;
        }
        
        // dp[i][j][k] = ways at round i, score diff j+n, last move k
        long[,,] dp = new long[n, 2*n+1, 3];
        char[] moves = {'F', 'W', 'E'};
        
        // Initialize first round
        for (int k = 0; k < 3; k++) {
            int score = GetScore(s[0], moves[k]);
            dp[0, score + n, k] = 1;
        }
        
        // Fill DP table
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= 2*n; j++) {
                for (int prevK = 0; prevK < 3; prevK++) {
                    if (dp[i-1, j, prevK] == 0) continue;
                    
                    for (int k = 0; k < 3; k++) {
                        if (k == prevK) continue; // Can't use same move consecutively
                        
                        int score = GetScore(s[i], moves[k]);
                        int newJ = j + score;
                        
                        if (newJ >= 0 && newJ <= 2*n) {
                            dp[i, newJ, k] = (dp[i, newJ, k] + dp[i-1, j, prevK]) % MOD;
                        }
                    }
                }
            }
        }
        
        // Sum all winning states (score > 0)
        long result = 0;
        for (int j = n + 1; j <= 2*n; j++) {
            for (int k = 0; k < 3; k++) {
                result = (result + dp[n-1, j, k]) % MOD;
            }
        }
        
        return (int)result;
    }
}

var countWinningSequences = function(s) {
    const MOD = 1000000007;
    const n = s.length;
    
    // Map creatures to numbers: F=0, W=1, E=2
    const charToNum = { 'F': 0, 'W': 1, 'E': 2 };
    
    // Returns points Bob gets when Alice plays a and Bob plays b
    const getPoints = (a, b) => {
        if (a === b) return 0;
        if ((a === 0 && b === 2) || (a === 1 && b === 0) || (a === 2 && b === 1)) return -1; // Alice wins
        return 1; // Bob wins
    };
    
    // dp[round][lastBobMove][scoreDiff] = number of ways
    // scoreDiff is offset by n to handle negative values (range: -n to n)
    const dp = Array(n).fill(null).map(() => 
        Array(3).fill(null).map(() => Array(2 * n + 1).fill(0))
    );
    
    // Initialize first round
    for (let bobMove = 0; bobMove < 3; bobMove++) {
        const aliceMove = charToNum[s[0]];
        const scoreDiff = getPoints(aliceMove, bobMove);
        dp[0][bobMove][scoreDiff + n] = 1;
    }
    
    // Fill DP table
    for (let round = 1; round < n; round++) {
        const aliceMove = charToNum[s[round]];
        
        for (let prevBobMove = 0; prevBobMove < 3; prevBobMove++) {
            for (let prevScoreDiff = 0; prevScoreDiff <= 2 * n; prevScoreDiff++) {
                if (dp[round - 1][prevBobMove][prevScoreDiff] === 0) continue;
                
                for (let bobMove = 0; bobMove < 3; bobMove++) {
                    if (bobMove === prevBobMove) continue; // Bob can't repeat moves
                    
                    const roundPoints = getPoints(aliceMove, bobMove);
                    const newScoreDiff = prevScoreDiff - n + roundPoints + n;
                    
                    if (newScoreDiff >= 0 && newScoreDiff <= 2 * n) {
                        dp[round][bobMove][newScoreDiff] = 
                            (dp[round][bobMove][newScoreDiff] + dp[round - 1][prevBobMove][prevScoreDiff]) % MOD;
                    }
                }
            }
        }
    }
    
    // Count winning sequences (Bob's score > Alice's score, i.e., scoreDiff > 0)
    let result = 0;
    for (let bobMove = 0; bobMove < 3; bobMove++) {
        for (let scoreDiff = n + 1; scoreDiff <= 2 * n; scoreDiff++) {
            result = (result + dp[n - 1][bobMove][scoreDiff]) % MOD;
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(n²) - 三重循环：n轮游戏 × 2n+1种分数差 × 3种移动选择
空间复杂度	O(n²) - DP数组大小为 n × (2n+1) × 3

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目