题目地址：
https://leetcode.com/problems/flip-game-ii/description/
给定一个长
n
n
n
的只含
'+', '-'
的字符串
s
s
s
，甲和乙轮流操作，每个人可以将
"++"
变为
"--"
，谁无法操作了谁就输。问甲是否必胜。
思路是记忆化搜索，如果某个局面是乙的必败态，则当前局面是甲的必胜态。直接枚举第一步操作即可。可以用记忆化加速，避免重复计算。代码如下：
class Solution {
public:
bool canWin(string s) {
unordered_map<string, bool> mp;
return dfs(s, mp);
}
bool dfs(string& s, unordered_map<string, bool>& mp) {
if (mp.count(s)) return mp[s];
for (int i = 0; i < s.size() - 1; i++)
if (s[i] == '+' && s[i + 1] == '+') {
s[i] = s[i + 1] = '-';
if (!dfs(s, mp)) {
s[i] = s[i + 1] = '+';
return mp[s] = true;
}
s[i] = s[i + 1] = '+';
}
return mp[s] = false;
}
};
时空复杂度
O
(
2
n
/
2
)
O(2^{n/2})
O
(
2
n
/
2
)
。