難度：★★★★☆
類型：數(shù)組
方法：動態(tài)規(guī)劃

力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄

題目

給定一個表示分數(shù)的非負整數(shù)數(shù)組。 玩家 1 從數(shù)組任意一端拿取一個分數(shù)，隨后玩家 2 繼續(xù)從剩余數(shù)組任意一端拿取分數(shù)，然后玩家 1 拿，…… 。每次一個玩家只能拿取一個分數(shù)，分數(shù)被拿取之后不再可取。直到?jīng)]有剩余分數(shù)可取時游戲結(jié)束。最終獲得分數(shù)總和最多的玩家獲勝。

給定一個表示分數(shù)的數(shù)組，預測玩家1是否會成為贏家。你可以假設每個玩家的玩法都會使他的分數(shù)最大化。

示例 1：

輸入：[1, 5, 2]
輸出：False
解釋：一開始，玩家1可以從1和2中進行選擇。
如果他選擇 2（或者 1 ），那么玩家 2 可以從 1（或者 2 ）和 5 中進行選擇。如果玩家 2 選擇了 5 ，那么玩家 1 則只剩下 1（或者 2 ）可選。
所以，玩家 1 的最終分數(shù)為 1 + 2 = 3，而玩家 2 為 5 。
因此，玩家 1 永遠不會成為贏家，返回 False 。

示例 2：

輸入：[1, 5, 233, 7]
輸出：True
解釋：玩家 1 一開始選擇 1 。然后玩家 2 必須從 5 和 7 中進行選擇。無論玩家 2 選擇了哪個，玩家 1 都可以選擇 233 。
最終，玩家 1（234 分）比玩家 2（12 分）獲得更多的分數(shù)，所以返回 True，表示玩家 1 可以成為贏家。

提示：

1 <= 給定的數(shù)組長度 <= 20.
數(shù)組里所有分數(shù)都為非負數(shù)且不會大于 10000000 。
如果最終兩個玩家的分數(shù)相等，那么玩家 1 仍為贏家。

解答

我們用動態(tài)規(guī)劃解決這一問題。

【數(shù)組定義】
定義二維數(shù)組dp，維度為n×n，其中n為nums數(shù)組的長度，dp[left][right]表示的是從left位置到right位置這個閉區(qū)間中的所有數(shù)字作為初始數(shù)組的話，先手在游戲結(jié)束時最終可以超過后手多少分數(shù)。dp中的數(shù)字可能有正有負，也有零。

【初始狀態(tài)】
很顯然，把所有l(wèi)eft=right位置，也就是斜對角線上的位置處的點填充為nums數(shù)組中對應位置。因為對于這些點，代表的物理含義是，如果游戲中數(shù)組只有一個元素，先手會優(yōu)于后手多少分？后手沒得選了，數(shù)組中的數(shù)字，就是先手最終優(yōu)于后手的分數(shù)。

【遞推公式】
對于left到right的閉區(qū)間組成的數(shù)組，先手（選手A）有且只有兩個選擇：
選擇left位置處的數(shù)字，也就意味著剩下的數(shù)字是從left+1到right的閉區(qū)間內(nèi)的，這時候要注意，接下來對于這段區(qū)間（從left+1到right），后手（選手B）就變成了先手（尤其要注意，這里理解很重要），而且選手B最終優(yōu)于選手A的分數(shù)為dp[left+1][right]，這樣的話，選手A獲得了nums[left]分數(shù)，減去選手B最終優(yōu)于選手A的分數(shù)，就是選手A最終優(yōu)于選手B的分數(shù)，也就是dp[left][right]=nums[left]-dp[left+1][right]，這里需要理解一下。

另一種狀況，選手A拿了最末尾的元素也就是，right所在位置的nums[right]，同理的，這時選手最終會A優(yōu)于選手B的分數(shù)為dp[left][right] = nums[right] - dp[left][right-1]。

我們從這兩種情況中選擇最大的，作為選手A游戲結(jié)束時超過選手B的分數(shù)：

dp[left][right] = max(nums[right]-dp[left][right-1], nums[left]-dp[left+1][right])

這里還涉及一個遍歷熟悉順序的問題，left需要從后往前遍歷，right需要從前往后遍歷，這樣做的目的是，充分利用已經(jīng)被填充的位置的結(jié)果，最終填充的dp數(shù)組是只有右上的直角三角形。

【返回值】
整個游戲數(shù)組最左端是零，結(jié)最右端位置是n-1，根據(jù)dp數(shù)組中每個位置的含義，我們返回dp[0][n-1]作為先手最終超過后手的分數(shù)，如果這個分數(shù)大于等于零，則先手獲勝。

class Solution:
    def PredictTheWinner(self, nums) -> bool:
        dp = [[nums[i] if i == j else 0 for i in range(len(nums))] for j in range(len(nums))]
        for left in reversed(range(len(nums)-1)):
            for right in range(left+1, len(nums)):
                dp[left][right] = max(nums[right]-dp[left][right-1], nums[left]-dp[left+1][right])
        return dp[0][-1] >= 0

如有疑問或建議，歡迎評論區(qū)留言~

有關更多力扣中等題的python解決方案，請移步力扣中等題解析