題目1025：除數(shù)博弈
愛麗絲和鮑勃一起玩游戲，他們輪流行動。愛麗絲先手開局。
最初，黑板上有一個數(shù)字 N 。在每個玩家的回合，玩家需要執(zhí)行以下操作：
1. 選出任一 x，滿足 0 < x < N 且 N % x == 0 。
2. 用 N - x 替換黑板上的數(shù)字 N 。
如果玩家無法執(zhí)行這些操作，就會輸?shù)粲螒颉?/p>
只有在愛麗絲在游戲中取得勝利時才返回 True，否則返回 false。假設(shè)兩個玩家都以最佳狀態(tài)參與游戲。
示例1：
輸入：2輸出：true解釋：愛麗絲選擇 1，鮑勃無法進行操作。
輸入：3輸出：false解釋：愛麗絲選擇 1，鮑勃也選擇 1，然后愛麗絲無法進行操作。
1 <= N <= 1000
分析
動態(tài)規(guī)劃問題，當前玩家在某個數(shù)字的成功失敗與否可以由更小的數(shù)字成功與否推斷出來，使用false_idx[]存儲會失敗的數(shù)字，1和3會失敗，先把數(shù)字1和3存儲在false_idx中，順序?qū)從4遍歷到N，對i的處理過程中，如果當前玩家可以選擇一個數(shù)字x，這個數(shù)字滿足i % x == 0，并且i - x在false_idx數(shù)組中，證明下個玩家一定會失敗，那當前玩家就一定會成功，根據(jù)當前玩家在當前數(shù)字成功失敗與否來更新false_idx數(shù)組。這道題還有數(shù)學方法奇偶性可以解，這里主要介紹動態(tài)規(guī)劃思路，數(shù)學方法有興趣大家可以自行搜索研究。
代碼
class Solution {public:bool divisorGame(int N) {if (N == 1 || N == 3) {return false;}if (N == 2) {return true;}vector<int> false_indexs;false_indexs.push_back(1);false_indexs.push_back(3);for (int i = 4; i <= N; ++i) {bool is_win = false;for (auto idx : false_indexs) {if (i % (i-idx) == 0) {is_win = true;break;}}if (!is_win) {false_indexs.push_back(i);}}return false_indexs.back() != N;}};