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); -- If people do not believe that mathematics is simple, it is because they do not realize how complicated life is. -- John Louis von Neumann --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.152.192 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1494929293.A.486.html