[LeetCode]Can I Win

和Flip Game类似，我们需要generate完整的game tree。当前节点结果取决于所有对手对应的子节点return的值，如果对手所有的选择无法获胜，return tree。对于对手的节点也是类似的，这道题maxchoosablenumber最多为20，所有我们用interger used记录用过的数字即可。并且game state也仅仅取决于used，因为如果用过的数组确定，那么desiredtotal剩下的数也是确定的。用memorization优化来避免重复的计算，假设限定1-n的数，时间复杂度O(n!)，对应所有游戏进行数字被取顺序的可能，空间复杂度一样。代码如下：

	class Solution {
	public:
	bool canIWin(int maxChoosableInteger, int desiredTotal)
	{
	if((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal)return false;
	unordered_map<int, bool> map;
	int used = 0;
	return canWin(maxChoosableInteger, desiredTotal, used, map);
	}
	private:
	bool canWin(int maxNum, int gap, int used, unordered_map<int, bool>& map)
	{
	if(map.find(used) != map.end())return map[used];
	for(int i = maxNum; i >= 1; --i)
	{
	if((used & (1 << i)) == 0)
	{
	if(i >= gap)
	{
	map[used] = true;
	return true;
	}
	bool win = canWin(maxNum, gap - i, used | (1 << i), map);
	if(!win)
	{
	map[used] = true;
	return true;
	}
	}
	}
	map[used] = false;
	return false;
	}
	};

view raw Can I Win.cpp hosted with ❤ by GitHub