LeetCode 3320. 统计能获胜的出招序列数 — Rust 实现

题意速览

• Alice 每回合固定出招 s[i] ∈ {F, W, E}

• Bob 每回合也出 {F, W, E}，但 不能连续两回合出相同生物

• 克制链：F 克 E，W 克 F，E 克 W（克制方得 1 分，相同则都不得）

• 求 Bob 总分 严格大于 Alice 总分的合法出招序列数，答案对 1e9+7 取模

映射：F→0, W→1, E→2

关键：只关心 Bob得分 − Alice得分 的差值 diff，不必分别追踪两人分数。

对于 Bob 出 b、Alice 出 a：

delta = (b - a + 3) % 3
  delta=0 → 相同     → diff+0
  delta=1 → b克制a   → diff+1  (Bob得分)
  delta=2 → a克制b   → diff-1  (Alice得分)

核心 DP

状态：dp[last][diff_idx] = 处理完当前回合、Bob最后一手出了 last、差值 diff = diff_idx - offset 的方案数

• last ∈ {0,1,2} 对应 F/W/E

• diff ∈ [-n, n]，用偏移 offset = n 映射到非负下标

• 转移时枚举下一手 b ≠ last，更新差值即可

时间 O(n² × 3 × 2)，空间 O(n)（滚动数组）

Rust 代码

const MOD: i64 = 1_000_000_007;

impl Solution {
    pub fn count_winning_sequences(s: String) -> i32 {
        let n = s.len();
        // 把 Alice 的出手映射为 0=F, 1=W, 2=E
        let alice: Vec<usize> = s
            .chars()
            .map(|c| match c {
                'F' => 0,
                'W' => 1,
                'E' => 2,
                _ => unreachable!(),
            })
            .collect();

        // offset 用来把 diff(可能为负的) 映射到数组下标
        // diff_idx = diff + offset,   diff ∈ [-n, n] → diff_idx ∈ [0, 2n]
        let offset = n as i64;

        // dp[last][diff_idx], last ∈ {0,1,2}
        let mut dp = vec![vec![0i64; 2 * n + 1]; 3];

        // ── 第 0 回合初始化（Bob 可以任选一手）──
        for b in 0..3 {
            let delta = (b as i64 - alice[0] as i64 + 3) % 3;
            let dc = if delta == 1 { 1 } else if delta == 2 { -1 } else { 0 };
            let idx = (dc + offset) as usize;
            dp[b][idx] = 1;
        }

        // ── 第 1 ~ n-1 回合 ──
        for i in 1..n {
            let mut ndp = vec![vec![0i64; 2 * n + 1]; 3];
            for last in 0..3 {
                for diff_idx in 0..=2 * n {
                    let cur = dp[last][diff_idx];
                    if cur == 0 {
                        continue;
                    }
                    for b in 0..3 {
                        if b == last {
                            continue; // 不能连续两手相同
                        }
                        let delta = (b as i64 - alice[i] as i64 + 3) % 3;
                        let dc = if delta == 1 { 1 } else if delta == 2 { -1 } else { 0 };
                        let new_idx = diff_idx as i64 + dc;
                        // 理论上 new_idx 一定在 [0, 2n] 内，防御式写一下
                        if new_idx >= 0 && new_idx <= 2 * n as i64 {
                            let ni = new_idx as usize;
                            ndp[b][ni] = (ndp[b][ni] + cur) % MOD;
                        }
                    }
                }
            }
            dp = ndp;
        }

        // ── 收集答案：diff > 0 即 diff_idx > n ──
        let mut ans = 0i64;
        for last in 0..3 {
            for diff_idx in (n + 1)..=2 * n {
                ans = (ans + dp[last][diff_idx]) % MOD;
            }
        }
        ans as i32
    }
}

执行流程示意（以 s = "FFF" 为例）

第0回合后只有 Bob出W(diff=+1)有1种，出E(diff=-1)有1种，出F(diff=0)有1种。

接着约束"不能重复"，逐步转移，最后 diff>0 的累计 = 3，匹配示例 ✅

复杂度

如果你要交到 LeetCode，函数签名可能需要包一层 struct Solution（上面的写法就是标准 LeetCode Rust 模板格式）。需要我补一个带 #[memo] / HashMap 的记忆化搜索版本作对照吗？