题目来源

• leetcode：294-vip.翻转游戏

题目描述

题目解析

题目要求先手必胜的方案，于是思路在于遍历所有的先手可能，对于每一个先手，一路玩下去，看当前先手策略是不是能让先手赢。

这道题不是问 “1p是否会怎么选都会赢”，而是 “如果1p每次都选特别的两个+，最终他会不会赢”。所以 canWin 这个函数的意思是 “在当前这种状态下，至少有一种选法，能够让他赢”。而 (!canWin) 的意思就变成了 “在当前这种状态下，无论怎么选，都不能赢”。所以 1p 要看的是，是否存在这样一种情况，无论 2p 怎么选，都不会赢。所以只要有一个 (!canWin)，1p 就可以确定他会赢。

class Solution {
    
public:
    bool canWin(string pattern){
    

        for (int i = 1; i < pattern.size(); ++i) {
    
            if(pattern[i] == '+' && pattern[i-1] == pattern[i]){
    
                pattern[i - 1] = pattern[i] = '-';
                if(!canWin(pattern)){
     // // 找到一个玩家A先手后玩家B就赢不了的先手策略
                    return true;
                }
                pattern[i - 1] = pattern[i] = '+';
            }
        }
        return false;
    }
};