877.md

877 Stone Game

Description

link

---

Trick

Alex can always take all odd piles or always take all even piles

Since sum of all piles is odd then sum of all odd piles won't equals sum of all even piles, Alex could just take the bigger ones.

Solution DP

dp[i][j] : the biggest number of stones you can get more than opponent picking piles in piles[i] ~ piles[j].

Recursive : dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])

Init : dp[i][i] = piles[i] // others zero

---

Code

Complexity T : O(n^2) M : O(n^2)

class Solution:
    def stoneGame(self, piles):
        """
        :type piles: List[int]
        :rtype: bool
        """
        n = len(piles)
        dp = [[0] * n for _ in range(n)]
        
        for i in range(n):
            dp[i][i] == piles[i]
        
        for d in range(1, n):
            for i in range(n - d):
                dp[i][i + d] = max(piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1])
        
        return dp[0][-1] > 0

Follow UP

Complexity T : O(n^2) M : O(n)

class Solution:
    def stoneGame(self, piles):
        """
        :type piles: List[int]
        :rtype: bool
        """
        n = len(piles)
        dp = piles[:]
        
        for d in range(1, n):
            for i in range(n - d):
                dp[i] = max(piles[i] - dp[i + 1], piles[i + d] - dp[i])
                
        return dp[0] > 0