Re: [問題] leetcode 464 can i win
看板Prob_Solve (計算數學 Problem Solving)作者cutekid (可愛小孩子)時間7年前 (2017/05/17 17:19)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/4 (看更多)
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://www.ptt.cc/bbs/Prob_Solve/M.1495012761.A.81D.html
推
05/18 00:58, , 1F
05/18 00:58, 1F
想法：
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
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
