题目描述

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 的不同出招序列的数量。

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

样例

输入： s = "FFF"

输出： 3

解释：

Bob 可以通过以下 3 种出招序列战胜 Alice："WFW"、"FWF" 或 "WEW"。
注意，其他如 "WWE" 或 "EWW" 的出招序列是无效的，因为 Bob 不能在连续两个回合中使用相同的生物。

输入： 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 <= 1000
• s[i] 是 'F'、'W' 或 'E' 中的一个。

算法

(动态规划) $O(n^2)$

1. 设状态 $f(i, j, k)$ 表示考虑了 Alice 前 $i$ 个出招，Bob 净胜分为 $j$，且 Bob 最后一次出招为 $k$ 的方案数。
2. 初始时，可以根据 Alice 第一个出招计算出来 $f(0)$ 对应的值。
3. 转移时，对于 $f(i, j, k)$，枚举上一次的出招 $k’$，然后根据当前 Alice 的出招和 $k$ 的值进行从 $f(i - 1)$ 进行转移。可以将转移关系写成一个矩阵方便代码编写。
4. 最终答案为 $j > 0$ 的所有 $f(n - 1, j, k)$ 的值。
5. 由于第一维每一轮仅与上一轮有关，所以可以用滚动数组优化第一维的状态表示。

时间复杂度

• 动态规划的状态数为 $O(n^2)$，转移时间为常数，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 优化状态后，需要 $O(n)$ 的额外空间存储状态。

C++ 代码

const int B = 1001;

class Solution {
private:
    int f[2][2 * B + 2][3];

public:
    int countWinningSequences(string s) {
        const int n = s.size();
        const int mod = 1000000007;
        const int w[3][3] = {
            {0, 1, -1},
            {-1, 0, 1},
            {1, -1, 0}
        };

        memset(f[0], 0, sizeof(f));

        if (s[0] == 'F')
            f[0][B][0] = f[0][B + 1][1] = f[0][B - 1][2] = 1;
        else if (s[0] == 'W')
            f[0][B - 1][0] = f[0][B][1] = f[0][B + 1][2] = 1;
        else
            f[0][B + 1][0] = f[0][B - 1][1] = f[0][B][2] = 1;

        for (int i = 1; i < n; i++) {
            int x;
            if (s[i] == 'F') x = 0;
            else if (s[i] == 'W') x = 1;
            else x = 2;

            memset(f[i & 1], 0, sizeof(f[i & 1]));

            for (int j = 1; j <= 2 * B; j++)
                for (int k = 0; k < 3; k++)
                    for (int k1 = 0; k1 < 3; k1++)
                        if (k != k1)
                            f[i & 1][j][k] = (
                                f[i & 1][j][k] +
                                f[(i - 1) & 1][j - w[x][k]][k1]
                            ) % mod;
        }

        int ans = 0;
        for (int j = B + 1; j <= 2 * B; j++)
            for (int k = 0; k < 3; k++)
                ans = (ans + f[(n - 1) & 1][j][k]) % mod;

        return ans;
    }
};