[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，其都有两种可能，'++'或者'--'，空间复杂度一样。代码如下：

	class Solution {
	public:
	bool canWin(string s) {
	if(map.find(s) != map.end())return map[s];
	int len = s.size();
	for(int i = 1; i < len; ++i)
	{
	if(s[i - 1] == '+' && s[i] == '+')
	{
	s[i] = '-';
	s[i - 1] = '-';
	bool win = canWin(s);
	s[i] = '+';
	s[i - 1] = '+';
	if(!win)
	{
	map[s] = true;
	return true;
	}
	}
	}
	map[s] = false;
	return false;
	}
	private:
	unordered_map<string, bool> map;
	};

view raw Flip Game II.cpp hosted with ❤ by GitHub