1. 題目

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

最初，黑板上有一個(gè)數(shù)字 N 。在每個(gè)玩家的回合，玩家需要執(zhí)行以下操作：

• 選出任一 x，滿足 0 < x < N 且 N % x == 0 。
• 用 N - x 替換黑板上的數(shù)字 N 。

如果玩家無法執(zhí)行這些操作，就會(huì)輸?shù)粲螒颉?/p>

只有在愛麗絲在游戲中取得勝利時(shí)才返回 True，否則返回 false。
假設(shè)兩個(gè)玩家都以最佳狀態(tài)參與游戲。

示例 1： 輸入：2 輸出：true 解釋：愛麗絲選擇 1，鮑勃無法進(jìn)行操作。示例 2： 輸入：3 輸出：false 解釋：愛麗絲選擇 1，鮑勃也選擇 1，然后愛麗絲無法進(jìn)行操作。提示： 1 <= N <= 1000

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/divisor-game
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

類似題目：

LeetCode 810. 黑板異或游戲（博弈推理）
LeetCode 5447. 石子游戲 IV hard（博弈DP）

• 如果N是奇數(shù)，奇數(shù)的約數(shù)只能是奇數(shù)，奇數(shù)減去奇數(shù)==偶數(shù)
  拿到奇數(shù)，偶數(shù)再-1有為奇數(shù)，拿到奇數(shù)必輸
• 如果N是偶數(shù)，我每次減1，讓對(duì)方是奇數(shù)，必贏

class Solution { public:bool divisorGame(int N) {//return N%2 == 0;return (N&1)==0;} };

0 ms 6 MB

---

動(dòng)態(tài)規(guī)劃

• win[n] 表示剩余數(shù)字是 n 的時(shí)候，勝算 true or false

class Solution { //C++ public:bool divisorGame(int N) {if(N == 1)return false;vector<bool> win(N+1,false);win[1] = false;win[2] = true;for(int Ni = 3, x; Ni <= N; ++Ni){ //當(dāng)前數(shù)字 Nifor(x = 1; x < Ni; ++x){ //我可以取小于 Ni 的 x，留給對(duì)手的數(shù)字是 Ni-xif(Ni%x == 0 && win[Ni-x]==false)//x可以取，且 留給對(duì)手的數(shù)使其失敗win[Ni] = true;//那我就贏了，哈哈}}return win[N];} };

12 ms 6.1 MB

class Solution: # py3def divisorGame(self, N: int) -> bool:if N == 1:return Falsedp = [False]*(N+1)dp[1] = Falsedp[2] = Truefor i in range(1, N+1):for j in range(1, i):if i%j == 0 and not dp[i-j]:dp[i] = Truereturn dp[N]

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1025. 除数博弈（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。