l*******a
发帖数: 36 | |
w****a
发帖数: 710 | 2 我理解的是，题目要求是running total，也就是两个人取数字的和超过一个数。
假设池子里还有三个数，1,2,3。要求达到的目标为5，两个玩家。
现在轮到玩家1取数字，如果贪心的取最大数字，则取3，total=3，那么玩家2随后取2
就能胜利。
如果玩家1不取3而是取1，total=1，玩家2无论从剩下的2和3里面取哪个数，他都必输。 |
l*******a
发帖数: 36 | |
s****n
发帖数: 199 | 4 如果可以重复选数字，那么如果 target % (maxChoosable + 1) == 0 那么玩家2必胜
，如果不是0那么玩家1第一步先拿到target % (maxChoosable + 1)，然后对应玩家2拿
的数字来拿 maxChoosable + 1 - player2Num，最后就刚好抢到target。
如果不可以重复选数字，有一个初步的想法，可以把这个问题转化成一个有2^
maxChoosable 个节点的图，开始在sum = 0的节点上，玩家1和2轮流walk，走到某些节
点时候会获胜。比如1 2 3 4, target = 10，玩家2的winning state是 1 2 3 4，玩家
1没有所以玩家2必胜；如果target = 9 玩家2的winning state是1 2 3 4，玩家1是2 3
4，所以玩家2只要拿到1就胜了，也是必胜；如果target = 8 玩家1多了1 3 4是
winning state，这时玩家1只要取4然后玩家2无论怎么取都会输。
但是感觉这个code实现起来太麻烦了，坐等楼下大神给出答案。 |
l*******a
发帖数: 36 | 5 嗯 同意你说的那个可选重复数字的那段。
不可选重复数字的我搜到了一个答案自己理解了下， 你看看？
http://blog.csdn.net/lsdtc1225/article/details/40342473
3
【在 s****n 的大作中提到】
: 如果可以重复选数字，那么如果 target % (maxChoosable + 1) == 0 那么玩家2必胜
: ，如果不是0那么玩家1第一步先拿到target % (maxChoosable + 1)，然后对应玩家2拿
: 的数字来拿 maxChoosable + 1 - player2Num，最后就刚好抢到target。
: 如果不可以重复选数字，有一个初步的想法，可以把这个问题转化成一个有2^
: maxChoosable 个节点的图，开始在sum = 0的节点上，玩家1和2轮流walk，走到某些节
: 点时候会获胜。比如1 2 3 4, target = 10，玩家2的winning state是 1 2 3 4，玩家
: 1没有所以玩家2必胜；如果target = 9 玩家2的winning state是1 2 3 4，玩家1是2 3
: 4，所以玩家2只要拿到1就胜了，也是必胜；如果target = 8 玩家1多了1 3 4是
: winning state，这时玩家1只要取4然后玩家2无论怎么取都会输。
: 但是感觉这个code实现起来太麻烦了，坐等楼下大神给出答案。
|
w****a
发帖数: 710 | 6 不能重复选的话，naive的做法就是求全排列然后一个一个试，O(n!)。
不知道有没有啥剪枝的办法。 |
