從LeetCode學演算法 - 100 Dynamic Programming (14)

1510. Stone Game IV (Hard)

寫在前面

扣掉第0篇外，這篇是100篇啦！！！**從開始寫以來，一路到現在其實也不容易，
雖然頻率因為工作和開課的關係降低很多，
但希望大家仍然從文章中能有所收穫。

100篇好像應該要來個感恩回饋(?)
那這樣好了，如果有任何問題，
歡迎在本篇底下發問(Python Taiwan也可以)，
同時請在Python Taiwan的連結本篇文的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

截止時間為7/31 23:59:59，這之後的留言問題我有看到還是會回答，
但就不會納入抽獎資格歐！

如果留言人數不足的話，
那我可能就以一篇文章的形式來回應大家的問題，
就不會進行抽獎囉XD

感謝大家的支持與肯定，期待我們都能從這當中(我寫文章，你們讀文章XD)
不斷成長，進而提升自己的程式能力！

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！面試篇已經全數上傳啦~
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/advleetcode

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode

Question

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero ** square number** of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1

1
2
3
Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2

1
2
3
Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3

1
2
3
Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4

1
2
3
4
5
Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0).
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5

1
2
3
Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

分析/解題

Alice和Bob玩不膩的撿石頭遊戲又來啦！
這次一樣是Alice先開始，一堆石頭裡面有n個石頭，每次玩家行動時，
可以選擇拿走某個非0的平方數的石頭數量，稱為一次行動。
(也就是1的平方、2的平方、3的平方…等)
當有人無法作任何行動的時候(也就是沒有任何石頭能拿)，就輸惹QQ
給定正整數n代表石頭的個數，如果Alice確定可以贏遊戲的話，
就回傳True，反之則回傳False。(假定雙方都採最佳的策略來進行)

由於每次要拿非0的平方數，所以不能pass，
這就保證了遊戲一定會結束，
因為最後一定會拿到空掉，下一個人會輸掉。

我們來考慮一下前面幾個狀況，來觀察一下有沒有什麼規律：
n = 0: False -> 顯然就是輸了嘛XD
n = 1: True -> Alice拿走1顆(1²)，由於拿光了，所以Alice贏。
n = 2: False -> Alice只能選擇拿1顆，Bob再拿1顆就沒了，Alice輸掉。
n = 3: True -> 只有1, 1, 1的選擇，所以Alice贏
n = 4: True -> Alice拿走4顆(2²)，直接獲勝

看起來好像沒有很明顯對吧？
但這邊可以從題目中思考到一個關鍵，由於雙方都是以最好的策略，
也就是Bob不會該贏卻沒贏 ，所以以下兩點是我們可以確定的：
1. 當n直接是完全平方數時，Alice可以贏
2. 當n=x會讓Bob贏(Alice輸)的時候，n在以下狀況時Alice會贏：
x+1, x+4, x+9, x+16…
因為這時候Alice只要拿掉對應的石頭，讓Bob碰到x的狀況，
這時候就反而變成Bob會輸了！
(Alice先拿會輸的狀況，換成Bob先拿也會輸)

由於這個狀況只限定於我們發現前一個False，
所以我們必須從已經確定的值去推論，
假設今天我們想要知道n = i的值是否為True ，
我們需要先知道n=0~i-1的值 ，
接著檢查是否有任何一個n=i-j² 的結果是False (留意j²要小於等於i )
只要有一個符合，那n=i的值就是True，
如果全部檢查完都沒有的話，n=i的值即為False。
由於n=i的值會跟前面n=i-j²的結果有關係，
這是一個很明顯的動態規劃的題目。

因此，我們的程式流程應該像這樣：

先初始化dp的陣列 ，其長度為n+1，並先全初始化成False。
執行一個迴圈，讓i從1~n (0已經是False了直接跳過) ：
2-1. 在裡面再開一個迴圈，讓j從1遞增到最大j² == i 為止
2-2. 若dp[i - j²]為False，將dp[i]設為True 並且break 離開這層迴圈
(已經確定True就不用往下找了)
整個雙層迴圈完成後，我們應該處理完成了整個dp的陣列，
只要回傳dp[n] 即可。

依此，寫成程式碼如下：

Java

Java的部分，由於boolean陣列初始化的預設值就是False，
就不用額外作初始化了。(C++的話還是記得要初始化啊！)
要使用ArrayList也可以，但長度確定固定的話，其實直接開陣列比較快。

Python

Python的部分，我們當然也可以一路append，
但直接初始化串列比較乾脆，內層的迴圈則使用while來檢查條件，
不要忘記每次將j遞增。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(n^(3/2))/O(n) 外層迴圈要跑n次，內層最大是根號n；
空間上使用dp的陣列/串列外，沒有額外的需求了)

相似及延伸

1140. Stone Game II (Medium)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

別忘了，要抽獎的讀者記得去Python Taiwan按讚留言分享歐！

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve