0294. 翻转游戏 II

ITCharge大约 3 分钟

---

0294. 翻转游戏 II

标签：记忆化搜索、数学、动态规划、回溯、博弈
难度：中等

题目链接

0294. 翻转游戏 II - 力扣

题目大意

描述：

你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下：

给定一个字符串 $currentState$ ，其中只含 '+' 和 '-'。你和朋友轮流将「连续」的两个 "++" 反转成 "--"。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。默认每个人都会采取最优策略。

要求：

请你写出一个函数来判定起始玩家是否存在必胜的方案：如果存在，返回 $true$ ；否则，返回 $false$ 。

说明：

$1 \le currentState.length \le 60$ 。
$currentState[i]$ 不是 '+' 就是 '-'。
不能有超过 $20$ 个连续的 '+'。
进阶：请推导你算法的时间复杂度。

示例：

示例 1：

输入：currentState = "++++"
输出：true
解释：起始玩家可将中间的 "++" 翻转变为 "+--+" 从而得胜。

示例 2：

输入：currentState = "+"
输出：false

解题思路

思路 1：记忆化搜索

这是一个博弈论问题，可以使用记忆化搜索来解决。核心思想是：当前玩家能否获胜，取决于是否存在一种操作，使得对手在剩余状态下无法获胜。

设 $f(s)$ 表示当前状态为字符串 $s$ 时，当前玩家是否能获胜。则： $f(s) = \bigvee_{i} f(s')$

其中 $s'$ 是将 $s$ 中第 $i$ 个位置的 "++" 翻转为 "--" 后得到的新状态， $\bigvee$ 表示逻辑或运算。

具体算法步骤：

遍历字符串，找到所有可以翻转的 "++" 位置。
对每个可翻转位置，模拟翻转操作得到新状态。
递归检查新状态下对手是否能获胜。
如果存在任何一个新状态使得对手无法获胜，则当前玩家获胜。
使用记忆化避免重复计算。

思路 1：代码

class Solution:
    def canWin(self, currentState: str) -> bool:
        # 使用记忆化搜索，避免重复计算
        memo = {}
        
        def dfs(state: str) -> bool:
            # 如果已经计算过，直接返回结果
            if state in memo:
                return memo[state]
            
            # 遍历字符串，寻找可以翻转的 "++"
            for i in range(len(state) - 1):
                if state[i] == '+' and state[i + 1] == '+':
                    # 模拟翻转操作：将 "++" 变为 "--"
                    new_state = state[:i] + "--" + state[i + 2:]
                    # 递归检查对手是否能获胜
                    # 如果对手无法获胜，则当前玩家获胜
                    if not dfs(new_state):
                        memo[state] = True
                        return True
            
            # 如果没有可翻转的位置，或者所有翻转都无法获胜
            memo[state] = False
            return False
        
        return dfs(currentState)

思路 1：复杂度分析

时间复杂度： $O(n \times 2^{n/2})$ ，其中 $n$ 是字符串长度。最坏情况下，每个状态都需要遍历所有可能的翻转位置，状态空间的大小约为 $2^{n/2}$ （因为每次翻转会减少 2 个字符）。
空间复杂度： $O(2^{n/2})$ ，用于存储记忆化结果，最坏情况下需要存储所有可能的状态。