題目

亞歷克斯和李用幾堆石子在做游戲。偶數(shù)堆石子排成一行，每堆都有正整數(shù)顆石子?piles[i]?。

游戲以誰手中的石子最多來決出勝負(fù)。石子的總數(shù)是奇數(shù)，所以沒有平局。

亞歷克斯和李輪流進(jìn)行，亞歷克斯先開始。 每回合，玩家從行的開始或結(jié)束處取走整堆石頭。 這種情況一直持續(xù)到?jīng)]有更多的石子堆為止，此時手中石子最多的玩家獲勝。

假設(shè)亞歷克斯和李都發(fā)揮出最佳水平，當(dāng)亞歷克斯贏得比賽時返回?true?，當(dāng)李贏得比賽時返回?false?。

示例：

輸入：[5,3,4,5]
輸出：true
解釋：
亞歷克斯先開始，只能拿前 5 顆或后 5 顆石子 。
假設(shè)他取了前 5 顆，這一行就變成了 [3,4,5] 。
如果李拿走前 3 顆，那么剩下的是 [4,5]，亞歷克斯拿走后 5 顆贏得 10 分。
如果李拿走后 5 顆，那么剩下的是 [3,4]，亞歷克斯拿走后 4 顆贏得 9 分。
這表明，取前 5 顆石子對亞歷克斯來說是一個勝利的舉動，所以我們返回 true 。

提示：

• 2 <= piles.length <= 500
• piles.length 是偶數(shù)。
• 1 <= piles[i] <= 500
• sum(piles)?是奇數(shù)。

解題思路

數(shù)組定義

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

狀態(tài)轉(zhuǎn)移

對于dp[i][j]，假設(shè)先手玩家為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;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 877. 石子游戏（dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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