翻转游戏 II

这个题解使用了博弈论中的 SG 定理。将初始的字符串 s 按照连续的 '+' 分割成多个子串，每个子串代表一个独立的游戏局面。对每个子串计算它的 SG 函数值，最后将所有 SG 函数值做异或操作，如果结果大于 0，则先手必胜，否则先手必败。 在计算单个子串的 SG 函数时，使用记忆化搜索 dfs(x)，其中 x 表示当前子串的长度。搜索过程中，枚举所有可能的分割方式，将分割后的两部分递归计算 SG 函数，并做异或操作，得到一个 SG 函数值的集合。最后，用 mex 函数找到最小的不属于这个集合的非负整数，作为当前状态的 SG 函数值。

时间复杂度: O(n^3)

空间复杂度: O(n)

```python
class Solution:
    def canWin(self, s: str) -> bool:
        def mex(vals):
            i = 0
            while i in vals:
                i += 1
            return i

        @cache
        def dfs(x):
            if x < 2:
                return 0
            vals = set()
            for a in range(x-1):
                b = x-a-2
                vals.add(dfs(a) ^ dfs(b))
            return mex(vals)

        plus = []
        l, r = 0, 0
        while r < len(s):
            if s[r] == '-':
                d = r-l
                if d >= 2:
                    plus.append(d)
                l = r + 1
            r += 1
        d = len(s) - l
        if d >= 2:
            plus.append(d)

        v = 0
        for x in plus:
            v^= dfs(x)
            
        return v > 0
```

注释：
1. `mex` 函数用于计算 mex 值，即找到最小的不属于给定集合的非负整数。
2. `@cache` 装饰器用于记忆化搜索，避免重复计算。
3. `dfs(x)` 函数用于计算当前状态的 SG 函数值，其中 `x` 表示当前子串的长度。
4. 首先将初始字符串按照连续的 '+' 分割成多个子串，存储在 `plus` 数组中。
5. 对于每个子串，调用 `dfs(x)` 计算其 SG 函数值，并将所有 SG 函数值做异或操作，得到最终结果 `v`。
6. 如果 `v > 0`，则先手必胜，否则先手必败。