877 Stone Game 石子游戲

Description:
Alice and Bob play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones across all the piles is odd, so there are no ties.

Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.

Example:

Example 1:

Input: piles = [5,3,4,5]
Output: true
Explanation:
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.

Example 2:

Input: piles = [3,7,2,3]
Output: true

Constraints:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles[i]) is odd.

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

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

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

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

示例 :

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

提示:

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

思路:

1. 貪心
   史上最簡單 medium
   由于石頭堆為偶數(shù), 且石頭總數(shù)為奇數(shù), 所以總能分出勝負(fù)
   計(jì)算奇數(shù) index 的和及偶數(shù) index 的和, 每次拿較大的 index 對(duì)應(yīng)的石頭堆必勝
   所以先手可以選擇必勝的策略
   時(shí)間復(fù)雜度為 O(1), 空間復(fù)雜度為 O(1)
2. 動(dòng)態(tài)規(guī)劃
   記 dp[i][j] 為取區(qū)間 [i, j] 能獲得的相對(duì)分?jǐn)?shù), 正數(shù)表示獲勝, 負(fù)數(shù)表示失敗, 0 表示平局
   dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
   雙方都會(huì)盡量找讓自己最大的得分
   最后比較 dp[0][n - 1] 和 0 的關(guān)系決定勝負(fù)
   時(shí)間復(fù)雜度為 O(n ^ 2), 空間復(fù)雜度為 O(n ^ 2)

代碼:
C++:

class Solution 
{
public:
    bool stoneGame(vector<int>& piles) 
    {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) dp[i][i] = piles[i];
        for (int i = 1; i < n; i++) for (int j = 0;j < n - i; j++) dp[j][i + j] = max(piles[j] - dp[j + 1][i + j], piles[i + j] - dp[j][i + j - 1]);
        return dp.front().back() > 0;
    }
};

Java:

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

Python:

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True