[leetcode] 877 stone game

Alice and Bob Playing games with piles of stones . There are even piles of stones , Line up ; Every pile has just A whole stone , The number is piles[i] .

Who has the most stones to decide the outcome of the game . Stony total yes Odd number , So there was no draw .

Alice and Bob Take turns ,Alice Let's start with . Every round , Players from the line Start or end Take away the whole pile of stones from . This continued until there were no more piles of stones , At this time, the hand Most stones The player win victory .

hypothesis Alice and Bob All at their best , When Alice Return when you win the game true , When Bob Return when you win the game false .

Example 1：

Input ： piles = [5,3,4,5]
Output ： true
explain ：
Alice Let's start with , Only the front 5 Or after 5 Stone .
Suppose he takes the front 5 star , This line becomes [3,4,5] .
If Bob Before taking it away 3 star , So the rest is [4,5],Alice After taking it away 5 Win 10 branch .
If Bob After taking it away 5 star , So the rest is [3,4],Alice After taking it away 4 Win 9 branch .
This shows that , Take before 5 A stone is right Alice It's a victory move , So back true .

Example 2：

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

Tips ：

• 2 <= piles.length <= 500
• piles.length yes even numbers
• 1 <= piles[i] <= 500
• sum(piles[i]) yes Odd number

Ideas

reference Predicting Winners A question

# Dynamic programming 
class Solution(object):
    def stoneGame(self, piles):
        n = len(piles)
        dp = [[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            dp[i][i] == 0
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                dp[i][j] = max((piles[i]-dp[i+1][j]),(piles[j]-dp[i][j-1]))
        return dp[0][n-1]>0