題目

https://leetcode-cn.com/problems/nim-game/

題解

本題實(shí)際上是一個(gè)需要分析的數(shù)學(xué)題。如果第一時(shí)間沒有發(fā)現(xiàn)規(guī)律的話，可以嘗試先用遞歸法，暴力輸出前幾個(gè)，觀察規(guī)律。

// 用本函數(shù)跑 1~100，找規(guī)律 public boolean canWin(int n) {if (n <= 3) return true;// canWinNim(n-1), canWinNim(n-2), canWinNim(n-3) 只要有一個(gè)為false本輪就能贏// 也就是說，除非都為true才返回false，否則本輪能贏返回truereturn !(canWin(n - 1) && canWin(n - 2) && canWin(n - 3)); }

輸出結(jié)果如下。

i=1, canwin=true
i=2, canwin=true
i=3, canwin=true
i=4, canwin=false
i=5, canwin=true
i=6, canwin=true
i=7, canwin=true
i=8, canwin=false
i=9, canwin=true
i=10, canwin=true
i=11, canwin=true
i=12, canwin=false
i=13, canwin=true
i=14, canwin=true
i=15, canwin=true
i=16, canwin=false
i=17, canwin=true
i=18, canwin=true
i=19, canwin=true
i=20, canwin=false

這樣，規(guī)律就顯而易見了，即：每逢 4 的倍數(shù)返回 false，其余都返回 true。

為什么會(huì)出現(xiàn)這樣的規(guī)律呢？實(shí)際上，是可以通過推理得到的：

面對(duì)4的整數(shù)倍的人，永遠(yuǎn)無法翻身，你拿N根對(duì)手就會(huì)拿4-N根，保證每回合共減4根，你永遠(yuǎn)對(duì)面4倍數(shù)，直到4。相反，如果最開始不是4倍數(shù)，你可以拿掉剛好剩下4倍數(shù)根，讓他永遠(yuǎn)對(duì)面4倍數(shù)。

發(fā)現(xiàn)這個(gè)規(guī)律之后，本題就很簡單了。代碼如下：

class Solution {public boolean canWinNim(int n) {return n % 4 != 0;} }

---

2021-11-16 二刷

題目

https://leetcode.com/problems/nim-game/

題解

DP空間超了，DP+空間優(yōu)化時(shí)間超了，只能數(shù)學(xué)解法。。

class Solution {public boolean canWinNim(int n) {// Approach 1: Recursive, Brute Force // return process(n);// Approach 2: DP // if (n <= 3) return true; // boolean[] dp = new boolean[n + 1]; // dp[0] = false; // dp[1] = true; // dp[2] = true; // dp[3] = true; // for (int i = 4; i <= n; i++) { // dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3]; // } // return dp[n];// Approach 3: DP + Space optimization // if (n <= 3) return true; // boolean[] dp = new boolean[4]; // dp[0] = false; // dp[1] = true; // dp[2] = true; // dp[3] = true; // int i = 3; // while (i++ <= n) { // dp[i % 4] = !dp[(i + 4 - 1) % 4] || !dp[(i + 4 - 2) % 4] || !dp[(i + 4 - 3) % 4]; // } // return dp[n % 4];// Approach 4: 玄學(xué)// 對(duì)dp數(shù)組[false, true, true, ture]進(jìn)行滾動(dòng)更新，當(dāng)除了自己以外其他3個(gè)均為true時(shí)結(jié)果為false，否則結(jié)果為true// 所以，滾動(dòng)更新了個(gè)寂寞，根本不需要更新return n % 4 != 0;}// 還剩n個(gè)石子的情況下，當(dāng)前玩家以先手姿態(tài)是否能贏 // public boolean process(int n) { // if (n <= 0) return false; // else if (n <= 3) return true; // // 只要有一種方法讓對(duì)方不能贏，那么我就能贏 // return !process(n - 1) || !process(n - 2) || !process(n - 3); // } }

總結(jié)

以上是生活随笔為你收集整理的leetcode 292. Nim Game | 292. Nim 游戏（DP-＞数学推理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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