題目

亞歷克斯和李用幾堆石子在做游戲。偶數堆石子排成一行，每堆都有正整數顆石子?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)?是奇數。

解題思路

數組定義

dp[i][j]表示對于子數組[i…j]，先手與后手玩家之間得分的差

狀態轉移

對于dp[i][j]，假設先手玩家為a，后手為b

• a玩家先拿的是piles[i]，那么取走piles[i]了以后，b玩家與a玩家得分的差距就是dp[i+1][j]
• a玩家先拿的是piles[j]，那么取走piles[j]了以后，b玩家與a玩家得分的差距就是dp[i][j-1]
  選擇得分更大的情況

代碼

class Solution {public boolean stoneGame(int[] piles) {int n=piles.length;int[][] dp = new int[n][n];for (int i = 0; i < n; i++) {dp[i][i]=piles[i];}for (int i=n-2;i>=0;i--){for (int j=i+1;j<n;j++)dp[i][j]= Math.max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1]);}return dp[0][n-1]>0;}
}