↓Skip to main content
  1. Posts/

LeetCode-3320 统计能获胜的出招序列数

·1 min·
Table of Contents

LeetCode-3320 统计能获胜的出招序列数 #

Solution 1 #

$dp[i][j][k]$ 代表序列 $i$ 处, 结算前得分为 $j$, 出招为 $k$, 最后能获胜的出招序列数. 根据规则递归, 注意 $i == n-1$ 时结算在下一步, 下一步的出招没有意义了, 所以要除以 $2$.

代码如下:

class Solution:
    def countWinningSequences(self, s: str) -> int:
        MOD = 1_000_000_007
        n = len(s)
        chs = {'F':0, 'W':1, 'E':2}

        @cache
        def f(i, j, k): 
            if i == n:
                return 1 if j > 0 else 0
            if j > n - i:
                return pow(2, n - 1 - i, MOD)
            elif -j >= n - i:
                return 0
            score = (k - chs[s[i]] + 3) % 3
            score = -1 if score == 2 else score
            res = (f(i + 1, j + score, (k + 1) % 3) + f(i + 1, j + score, (k + 2) % 3)) % MOD
            return res // 2 if i == n - 1 else res

        return (f(0, 0, 0) + f(0, 0, 1) + f(0, 0, 2)) % MOD