前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的464题。
问题描述
在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到 100 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？
你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。
示例 1：
输入：
maxChoosableInteger = 10
desiredTotal = 11
输出：
false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
分析：
我的想法是，采用回溯法。相同的一层是自身计算过程，则下一层则代表对手的计算过程。只要能将对手计算逼迫到输，则返回成功否则返回失败；下一层，也就是对手环节也会将自身的对手逼迫到输，若能则返回成功否则返回失败。
如下是我写的代码，然而超出时间限制。
func canIWin(maxChoosableInteger int, desiredTotal int) bool {
if desiredTotal <= maxChoosableInteger {
return true
}
if desiredTotal * 2 > (1 + maxChoosableInteger) * maxChoosableInteger {
return false
}
return canWin(maxChoosableInteger, desiredTotal, []int{})
}
func exist(a int, num []int) bool {
for i := 0; i < len(num); i++ {
if a == num[i] {
return true
}
}
return false
}
func canWin(maxChoosableInteger int, desiredTotal int, record []int ) bool {
if desiredTotal <= 0 {
return false
}
for i := 1; i <= maxChoosableInteger; i++ {
if exist(i, record) {
continue
}
flag := canWin(maxChoosableInteger, desiredTotal-i, append(record, i))
if flag == false {
return true
}
}
return false
}
然后参考了一下柳婼的代码
分析：两个特殊情况：1.如果能够选的最大数字大于等于desiredTotal，第一个人又不傻肯定选最大的值，那样他就赢即：
if(maxn >= desiredTotal) return true;
2.如果所有能够选的数字的总和都小于desiredTotal，再怎么选两个人都不可能赢，所以肯定输：
总和就是首项加末项的和乘以项数除以2：if((1 + maxn) * maxn / 2 < desiredTotal) return false;
然后建立一个canWin函数，需要用visited标记某个数字是否被选过。因为可选的数字最大不超过20，则可以用一个整型数组标记，因为整型有32位，如果1被选过就把第1位（不是第0位，当然也可以从0开始）标记为1，如果2被选过就把第2位标记为1，这样保证所有数字不重复
所以传入两个值，一个是想要达到（或者说超过，也就是大于等于啦）的目标数字target，另一个是visited数字标记哪些数字被选过了
用map标记当前情况在map表中是否存在，存在的话结果保存在map里面，如果我们发现这个visited也就是这个数字选择的情况已经被保存过了，就直接返回在map里面保存的结果
遍历i从1到maxn（maxn是可以选择的最大值，即maxChoosableInteger），表示考虑选择i的情况，用mask = 1 « i，如果mask和visited进行与运算，如果等于0说明当前的visited没有被访问过，就可以考虑这个i的情况，如果要选的这个i大于target，不傻的这个人就会选择i因为肯定能赢，还有种情况自己能赢，就是对方输了，即：canWin(target - i, mask | visited) == false，（mask | visited表示把i那位也标记为1）这个时候把visited情况存起来并且return true，表示赢了，如果所有数字都遍历完还是没有return true，那就最后return false，return false之前不要忘记把当前状态存储起来，也就是m[visited] = false;
class Solution {
private:
int maxn;
map<int, bool> m;
public:
bool canIWin(int maxChoosableInteger, int desiredTotal) {
maxn = maxChoosableInteger;
if(maxn >= desiredTotal) return true;
if((1 + maxn) * maxn / 2 < desiredTotal) return false;
return canWin(desiredTotal, 0);
}
bool canWin(int target, int visited) {
if(m.find(visited) != m.end()) return m[visited];
for(int i = 1; i <= maxn; i++) {
int mask = (1 << i);
if((mask & visited) == 0 && (i >= target || canWin(target - i, mask | visited) == false)) {
m[visited] = true;
return true;
}
}
m[visited] = false;
return false;
}
};
其实上面思想是相通的，多了两个精妙的优化。
1 采用int类型来存访问过的（题干中maxChoosableInteger不超过20）
2 map中存计算过结果
var m map[int]bool
func canIWin(maxChoosableInteger int, desiredTotal int) bool {
if desiredTotal <= maxChoosableInteger {
return true
}
if desiredTotal * 2 > (1 + maxChoosableInteger) * maxChoosableInteger {
return false
}
m = make(map[int]bool)
return canWin(maxChoosableInteger, desiredTotal, 0)
}
func canWin(maxChoosableInteger int, desiredTotal int, record int) bool {
if desiredTotal <= 0 {
m[record] = false
return false
}
if ret, ok := m[record]; ok {
return ret
}
for i := 1; i <= maxChoosableInteger; i++ {
mask := 1 << uint(i)
if (mask & record) != 0 {
continue
}
flag := canWin(maxChoosableInteger, desiredTotal-i, mask|record)
if flag == false {
m[record] = true
return true
}
}
m[record] = false
return false
}
总结：
勤思考。
结语
不管怎么样好好加油。
