###### tags: `Leetcode` `medium` `dynamic programming` `python`

# 486. Predict the Winner

## [題目連結:] https://leetcode.com/problems/predict-the-winner/

## 題目:
You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.


#### [圖片來源:] https://leetcode.com/problems/predict-the-winner/

## 解題思路:
* 題目說 player1,player2玩家分別每次可以選頭或尾的數，最後比較其加總，若player1贏or平手，return True

* dp[i][j]: **從nums[i]~nums[j] 先下手拿的玩家情況下能獲利多少**
* 初始定義dp[i][i]=nums[i] for i in range(len(nums))
* 因為只有一個數，player1拿一定獲利+nums[i]
* 從i從(尾-1)往頭進行遍歷，j從(i+1)往尾進行遍歷
* 每次當前player要拿時，考慮拿頭nums[i] or 尾 nums[j]
* 拿頭: 則獲利為下個人從nums[i+1]~nums[j]進行選擇: **nums[i]-dp[i+1][j]**
* 拿尾: 則獲利為下個人從nums[i]~nums[j-1]進行選擇: **nums[j]-dp[i][j-1]**
* 方程式為: **dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])**
* 因為player1先選，最後判斷dp[0][-1]>=0即可

## Python:

class Solution(object):
    def PredictTheWinner(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        #dp[i][j]:從nums[i]~nums[j] 先下手拿的玩家情況下能獲利多少
        dp=[[0 for _ in range(len(nums))] for _ in range(len(nums))]
        #init
        for i in range(len(nums)):
            dp[i][i]=nums[i]
        #dp
        for i in range(len(nums)-2,-1,-1):
            for j in range(i+1,len(nums)):
                #choose head or tail
                dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
        return dp[0][-1]>=0 

if __name__ == '__main__':
    result=Solution()
    ans=result.PredictTheWinner(nums = [1,5,233,7])
    print(ans)