# 0877. 石子游戲 ## 題目地址(877. 石子游戲) <https://leetcode-cn.com/problems/stone-game/> ## 題目描述 ``` <pre class="calibre18">``` 亞歷克斯和李用幾堆石子在做游戲。偶數堆石子排成一行，每堆都有正整數顆石子 piles[i] 。 游戲以誰手中的石子最多來決出勝負。石子的總數是奇數，所以沒有平局。 亞歷克斯和李輪流進行，亞歷克斯先開始。 每回合，玩家從行的開始或結束處取走整堆石頭。 這種情況一直持續到沒有更多的石子堆為止，此時手中石子最多的玩家獲勝。 假設亞歷克斯和李都發揮出最佳水平，當亞歷克斯贏得比賽時返回 true ，當李贏得比賽時返回 false 。 示例： 輸入：[5,3,4,5] 輸出：true 解釋： 亞歷克斯先開始，只能拿前 5 顆或后 5 顆石子 。 假設他取了前 5 顆，這一行就變成了 [3,4,5] 。 如果李拿走前 3 顆，那么剩下的是 [4,5]，亞歷克斯拿走后 5 顆贏得 10 分。 如果李拿走后 5 顆，那么剩下的是 [3,4]，亞歷克斯拿走后 4 顆贏得 9 分。 這表明，取前 5 顆石子對亞歷克斯來說是一個勝利的舉動，所以我們返回 true 。 提示： 2 <= piles.length <= 500 piles.length 是偶數。 1 <= piles[i] <= 500 sum(piles) 是奇數。 ``` ``` ## 前置知識 - 動態規劃 ## 公司 - 阿里 - 字節 ## 思路 由于 piles 是偶數的，并且 piles 的總和是奇數的。 因此 Alex`可以做到`要不拿的全部是奇數，要么全部是偶數。 舉個例子： 比如 Alex 第一次先拿第一個 這里有兩種情況： 1. Lee 如果拿了第二塊（偶數），那么 Alex 繼續拿第三塊，以此類推。。。 2. Lee 如果拿了最后一塊（偶數），那么 Alex 繼續拿倒數第二塊，以此類推。。。 因此 Alex`可以`做到只拿奇數或者偶數，只是他可以控制的，因此他要做的就是數一下，奇數加起來多還是偶數加起來多就好了。 奇數多就全部選奇數，偶數就全部選偶數。 Lee 是沒有這種自由權的。 ## 關鍵點解析 - 可以用 DP（動態規劃） - 可以從數學的角度去分析 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {number[]} piles * @return {boolean} */</span> <span class="hljs-keyword">var</span> stoneGame = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">piles</span>) </span>{ <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; }; ``` ``` ## 擴展 騰訊面試題：一共 100 只弓箭 你和你的對手共用。你們每次只能射出一支箭或者兩支箭，射擊交替進行，設計一個算法，保證自己獲勝。 答案： 先手，剩下的是 3 的倍數就行（100-1=99），然后按照 3 的倍數射箭必贏。 比如你先拿了 1，剩下 99 個。 對手拿了 1，你就拿 2。這樣持續 33 次就贏了。如果對手拿了 2 個，你就拿 1 個，這樣持續 33 次你也是贏的。 > 這是一種典型的博弈問題， 你和對手交替進行，對手的行動影響你接下來的策略。 這算是一種最簡單的博弈問題了