1. 玩家1和玩家2交替選擇數字。
第一次到第三次選擇會是玩家1，玩家2，玩家1。
對於第三次選擇的時候，
第一次選1，第二次選2和第一次選2，第二次選1，實際上是沒有差別的。
使用map紀錄1和2被選的樣態，相同樣態直接取結果對遞迴截枝。
2. 最佳化的判斷，在所有可能有一成立即成立，直接函數返回加速。
AC, 1s
https://github.com/jamalch-tw/oj/blob/master/LeetCode/464.cpp
※ 引述《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);

我這邊卡住的點是 b如果沒選到最佳的 可能a就贏了所以感覺不能窮舉全部選擇 不知道該如何處理?看你的做法是全部考慮？ 所以是我哪邊想錯了嗎？好像有點懂了 我在想一下XD不過你的做法跟我看不懂那個應該是等價的只是他合成同一個, 比較難懂, 你的分開player處理比較容易看懂 XD

合成一個的技術叫做 Negamax https://goo.gl/Mpb3O4使用 map 的技術叫做 transposition tablehttps://goo.gl/RJgN60 先找本 AI 的書研究一下比較容易懂

也太複雜, 一堆詞都沒聽過...謝謝各位 我研究研究

negamax 的原理其實就只是 min(a,b) = -max(-a,-b)所以 min 層的動作可以跟 max 層動作相同但取負號其實這以 min 層玩家的視點來看也是很合理的對對手極好的結果對自己就是極糟於是就能把「最小化對手得分」轉化成「最大化"自己"得分」以最大化自己得分這個觀點來說兩個玩家的動作其實是一樣的把以上這一些總結起來就是 negamax 演算法了

推 L 大，「零和遊戲」利用取負號(取代min、max層的判斷)