題目連結：
題目意譯：
在 "100 game" 中，兩位玩家將會輪流加上某個介於 1（含）到 10（含）之間的數字到一個持續累積的總和值。哪個玩家先讓累積的總和值達到或是超過 100 則將會贏得遊戲。
假如我們將上面的遊戲變成「不得重複使用先前的整數」呢？
What if we change the game so that players cannot re-use integers?
例如說，兩位玩家可能會從一個由數字 1（含）到 15（含）所組成的「公共池」挑出數字且不放回去池中，直到得到總和值 ≧ 100。
給定兩整數 maxChoosableInteger 以及 desiredTotal。如果第一位玩家（譯者注：指先手玩家）可以必贏，則回傳真（True）；反之，則回傳假（False）。假設兩位玩家按照最佳策略遊玩此遊戲。
限制：
1 ≦ maxChoosableInteger ≦ 20
0 ≦ desiredTotal ≦ 300
範例測資：
範例 1：
輸入： maxChoosableInteger = 10, desiredTotal = 11
輸出： false
解釋：
無論第一位玩家選哪個數字，該玩家必輸。
第一位玩家可以選擇 1 到 10 的某個數字。
如果第一位玩家選擇 1，則第二位玩家可以選擇 2 到 10 的某個數字。
第二位可以選擇 10 並贏得遊戲，此時總和值 = 11，其 ≧ desiredTotal。
第一位玩家選擇其他整數也是同理，第二位玩家一定會贏。
範例 2：
輸入： maxChoosableInteger = 10, desiredTotal = 0
輸出： true
範例 3：
輸入： maxChoosableInteger = 10, desiredTotal = 1
輸出： true
解題思維：
其實跟這題很像，只是現在我們可以用一個 maxChoosableInteger 位元的整數來代表「現在」哪些整數已經被選了（進而可以算出「現在」的總和值）的「狀態」。
當然如果 (maxChoosableInteger + 1) × maxChoosableInteger ÷ 2 < desiredTotal 的話，代表所有整數加總都無法超過 desiredTotal。進而代表著兩位玩家都不可能贏，因此回傳假。
如果把兩位玩家都贏不了的情況篩選掉之後，則我們可以按照平常的方式使用動態規劃（Dynamic Programming，DP）來得出第一位玩家是否必贏。
定義一個陣列 D，其中 D[i] 代表著在選擇整數的「狀態」為 i 的情況下（參見上面提及用整數代表「狀態」的部份）現在「要選下一個數字的玩家」是否必贏。根據此定義，所求為 D[0] 之值。
可以看到遞迴式為：
如果存在某個整數 j 使得 (i & (j - 1) == 0)（這代表著 j「現在」還沒被選過）且 Si + j ≧ desiredTotal，則 D[i] = true；
又或是如果存在某個整數 j 使得 (i & (j - 1) == 0) 且 D[i + 2 ^ (j - 1)] = false（這代表著如果此時選了 j 之後，對方必輸），則 D[i] = true；
如果以上皆非，則 D[i] = false。
接著我們從 D[0] 開始遞迴求解。注意同一個 i 值可能會被重複求解，如果已經求過了就直接挪用先前的 D[i] 之值即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
