作者cutekid (可爱小孩子)
看板Prob_Solve
标题Re: [问题] leetcode 464 can i win
时间Wed May 17 17:19:19 2017
Retrograde Method:
http://codepad.org/i3CsFKnT (Perl)
不知道有没有写错
还请各位帮我看看
※ 引述《powertodream (The Beginning)》之铭言：
: 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);
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.221.80.36
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1495012761.A.81D.html
1F：推 powertodream: 看不懂 可以分享想法吗？ 05/18 00:58
想法：
1. 用二进位做状态编码
Ex. MAX = 5, (5,4,1) ，则 state = 11001
(4,3,2,1)，则 state = 01111
2. 一开始初始所有状态值都是「输型」(值为: 0)
3. 从最後一个状态(所有数字都取的状态)开始往前推 (Retrograde Method)
4. 当前状态是输型的话，则把当前状态拿掉一个数字後(假设叫: 先前状态)
设先前状态为「赢型」(值为: 1)
ps. 如果拿掉一个数字後(剩余数字和) >= desiredTotal，略过不做事情
5. 当前状态是赢型的话，略过不做事情
6. 最後看第一个状态(所有数字都不取的状态)，是输型还是赢型即可
※ 编辑: cutekid (210.61.233.210), 05/18/2017 14:15:46