LC 3320. Count The Number of Winning Sequences

https://leetcode.com/problems/count-the-number-of-winning-sequences/description/

Tag: DP

typedef long long ll;
class Solution {
public:
    int countWinningSequences(string s) {
        ll mod = 1e9 + 7;
        int n = s.size();
        unordered_map<char, array<int, 3>> mp;
        mp['F'] = {0, 1, -1};
        mp['W'] = {-1, 0, 1};
        mp['E'] = {1, -1, 0};

        // n -> 0, n - 1 -> -1, n + 1 -> 1
        int base = n;
        vector<vector<vector<ll>>> f(n, vector<vector<ll>>(3, vector<ll>(2 * n + 1, 0)));

        for (int i = 0; i < 3; i++) {
            f[0][i][base + mp[s[0]][i]] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int pre = 0; pre < 3; pre++) {
                for (int cur = 0; cur < 3; cur++) {
                    if (pre == cur) continue;
                    for (int j = 0; j <= 2 * n; j++) {
                        if (f[i - 1][pre][j] == 0) continue;
                        f[i][cur][j + mp[s[i]][cur]] += f[i - 1][pre][j];
                        f[i][cur][j + mp[s[i]][cur]] %= mod;
                    }
                }
            }
        }

        ll ans = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = n + 1; j <= 2 * n; j++) {
                ans = (ans + f[n - 1][i][j]) % mod;
            }
        }
        return ans;
    }
};

本題主要的重點是在變換勝負以及平局的計算方法，如果我們以直覺的方式來保存勝或是負就會發現我們無法判斷到底點數是否比較多。

所以我們這邊進行轉換，改成如果勝場就 +1 敗場就 -1 遇到平局就不變，這樣只要最終的結果是大於 0 就表示勝場比較多。

那由於 DP 需要使用到陣列儲存，但是又不可以有負的 index ，所以我們可以進行平移讓 0 變成 n，此時就可以發現可以使用 0 ~ 2 * n 大小的陣列來表示。