愛麗絲和鮑勃一起玩游戲，他們輪流行動。愛麗絲先手開局。

最初，黑板上有一個數字?n?。在每個玩家的回合，玩家需要執行以下操作：

• 選出任一?x，滿足?0 < x < n?且?n % x == 0?。
• 用?n - x?替換黑板上的數字?n?。

如果玩家無法執行這些操作，就會輸掉游戲。

只有在愛麗絲在游戲中取得勝利時才返回?true?。假設兩個玩家都以最佳狀態參與游戲。

示例 1：

輸入：n = 2
輸出：true
解釋：愛麗絲選擇 1，鮑勃無法進行操作。

示例 2：

輸入：n = 3
輸出：false
解釋：愛麗絲選擇 1，鮑勃也選擇 1，然后愛麗絲無法進行操作

數學歸納法：

class Solution {
public:bool divisorGame(int n) {return n%2==0;  }
};

數學歸納法的核心是：

1. 基礎步：驗證?n?取最小的幾個值時猜想成立；
2. 歸納步：假設?n ≤ k?時猜想成立，證明?n = k+1?時猜想也成立。

1. 基礎步：n=1 和 n=2 時結論成立

• n=1（奇數）：1 沒有小于自身的因數（無法操作），先手必敗（符合猜想）。
• n=2（偶數）：2 的因數是 1，先手減去 1 后剩 1，后手無法操作，先手必勝（符合猜想）。

2. 歸納步：假設 n≤k 時成立，證明 n=k+1 時成立

分兩種情況討論?k?的奇偶性（因為?k?和?k+1?奇偶性相反）：

情況 1：k 是偶數 → k+1 是奇數

• n = k+1?是奇數，其所有因數?x?必為奇數（奇數的因數都是奇數）。
• 先手（Alice）必須減去一個奇數?x，剩余數為?(k+1) - x：
  • 奇數減奇數 = 偶數，且?(k+1) - x ≤ k（因為?x ≥ 1）。
  • 根據歸納假設（n ≤ k?時成立），偶數必為必勝態，此時輪到后手（Bob）面對偶數，Bob 必勝。
• 結論：n=k+1（奇數）時，Alice 必敗（符合猜想）。

情況 2：k 是奇數 → k+1 是偶數

• n = k+1?是偶數，其因數?x?可以是奇數或偶數。
• 先手（Alice）可以選擇減去一個奇數?x，剩余數為?(k+1) - x：
  • 偶數減奇數 = 奇數，且?(k+1) - x ≤ k（因為?x ≥ 1）。
  • 根據歸納假設（n ≤ k?時成立），奇數必為必敗態，此時輪到后手（Bob）面對奇數，Bob 必敗。
• 結論：n=k+1（偶數）時，Alice 可以通過選擇合適的?x?讓 Bob 必敗，因此 Alice 必勝（符合猜想）。

最終結論

通過數學歸納法，證明了 “偶數時先手必勝，奇數時先手必敗” 的猜想成立。

本質邏輯：奇數的因數都是奇數，操作后必然留下偶數（給對手必勝態）；而偶數可以通過減去奇數留下奇數（給對手必敗態），因此奇偶性直接決定了勝負。

動態規劃：?

class Solution {
public:bool divisorGame(int n) {// 創建一個布爾類型數組R，大小為n，用于記錄每個數字的先手狀態// R[i]表示：當數字為i時，當前玩家（先手）是否能獲勝（true為勝，false為敗）vector<bool> R(n, false);// 基礎情況：// 當數字為1時，沒有小于1的因數，先手無法操作，必敗R[1] = false;// 當數字為2時，先手可以取因數1，剩余1給對手（對手必敗），因此先手必勝R[2] = true;// 從數字3開始，依次推遞推計算每個數字的勝負狀態for(int i = 3; i < n + 1; i++) {// 枚舉當前數字i的所有可能因數j（1 ≤ j < i）for(int j = 1; j < i; j++) {// 核心判斷：// 1. j必須是i的因數（i % j == 0）// 2. 取走j后，剩余數字i-j對應的狀態為必敗（!R[i-j]）// 如果存在這樣的j，說明當前玩家可以通過取j讓對手陷入必敗態，因此當前玩家必勝if(i % j == 0 && !R[i - j]) {R[i] = true;  // 標記當前數字i為必勝態break;        // 找到一個有效j即可，無需繼續枚舉}}}// 返回數字n對應的先手狀態（是否必勝）return R[n];}
};

?

通過定義狀態?f[i]?記錄 “當前數字為?i?時，先手是否必勝”，再從基礎情況遞推到更大的?i。

1. 狀態定義

• f[i] = true：當數字為?i?時，先手必勝；
• f[i] = false：當數字為?i?時，先手必敗。

2. 遞推邏輯（核心）

對于數字?i，先手的勝負取決于其所有可能的下一步操作：

• 先手可以選擇?i?的任意一個因數?j（0 < j < i），將數字變為?i-j（此時輪到后手操作，后手面對的狀態是?f[i-j]）；
• 如果存在至少一個?j，使得?f[i-j] = false（即后手面對?i-j?時必敗），那么先手可以選擇這個?j，讓后手陷入必敗態，因此?f[i] = true（先手必勝）；
• 如果對于所有?j，都有?f[i-j] = true（即后手面對所有可能的?i-j?時都必勝），那么先手無論怎么操作都會讓后手必勝，因此?f[i] = false（先手必敗）。

3. 基礎情況（邊界條件）

• f[0]：無意義（無法操作）；
• f[1]：數字 1 沒有小于自身的因數（j?不存在），先手無法操作，必敗 →?f[1] = false；
• f[2]：因數?j=1，操作后變為?2-1=1，此時后手面對?f[1]=false（必敗），因此?f[2] = true（先手必勝）。

4. 遞推過程（從前往后計算）

從?i=3?開始，依次計算?f[i]：

• 枚舉?i?的所有因數?j（0 < j < i）；
• 對每個?j，檢查?f[i-j]?是否為?false；
• 只要存在一個?j?滿足?f[i-j] = false，則?f[i] = true；否則?f[i] = false。

示例說明（以?i=3?為例）

• i=3?的因數?j?為?1（因為?3?的因數是?1?和?3，但?j < 3，所以只有?j=1）；
• 操作后數字變為?3-1=2，此時后手面對?f[2] = true（后手必勝）；
• 由于所有可能的?j?對應的?f[i-j]?都是?true，因此?f[3] = false（先手必敗）。

本質邏輯

• 博弈問題的核心是 “讓對手陷入必敗態”；
• 動態規劃通過記錄每個狀態的勝負，將大問題拆解為小問題（i?的狀態依賴于更小的?i-j?的狀態）；
• 從基礎情況逐步遞推，最終可得到任意?n?對應的?f[n]，即初始狀態下先手的勝負。

?

?

?