https://leetcode.com/problems/can-i-win/#/description
是两个人互相取数字, 当第一个人取的数字超过目标, 就return true
原本的想法是, player 1 挑全部没选过的number, 然后 呼叫secondPlayerWin的
function
去判断是不是有存在secondPlayer win的, 只要有存在A 选的这个number就是不行的
不过写不太好的吃了个wrong answer,
偷看看讨论串解答
看了很多的作法, 都是做类似
!helper(desiredTotal - i)
的递回,
想半天仍然不太懂... 有版友有兴趣一起研究研究吗?
这个是原作者的解释, 但是我仍然不懂他的意思, 为什么code要写成那样
**
The strategy is we try to simulate every possible state. E.g. we let this
player choose any unchosen number at next step and see whether this leads to
a win. If it does, then this player can guarantee a win by choosing this
number. If we find that whatever number s/he chooses, s/he won't win the
game, then we know that s/he is guarantee to lose given such a state.
// try every unchosen number as next step
for(int i=1; i<used.length; i++){
if(!used[i]){
used[i] = true;
// check whether this lead to a win, which means
helper(desiredTotal-i) must return false (the other player lose)
if(!helper(desiredTotal-i)){
map.put(key, true);
used[i] = false;
return true;
}
used[i] = false;
}
}
map.put(key, false);