[LeetCode]Flip Game II

Game类的题目，假设有一个对手并且每次都是optimal move，判断是否能赢。依然是DFS解法的题目，我们要generate完整的game tree，然后当前节点对于每一次当前玩家的选择，子节点对于对手的选择。可以明确的是，如果基于当前状态，枚举所有的选择进而生成所有的子节点，如果所有子节点对应的对手的状态都无法取胜的话，那么我们可以明确当前的节点的move可以取胜，return true。同理对于对手的节点，逻辑也是一样的。我们只需要看return到root的时候结果是什么即可。单纯的递归有很多重复的计算，因为game的state可以单纯地用input string来表示，所有我们用memorization来优化即可。假设输入string长度为n，时间复杂度O(2^(n / 2))，因为对于任意连续的char，其都有两种可能，'++'或者'--'，空间复杂度一样。代码如下：