1690. Stone Game VII (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def stoneGameVII(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        n = len(stones)
        sums = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                if i == j:
                    sums[i][j] = stones[i]
                else:
                    sums[i][j] = sums[i][j - 1] + stones[j]
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                dp[i][j] = max(sums[i + 1][j] - dp[i + 1][j], sums[i][j - 1] - dp[i][j - 1])
        return dp[0][-1]

        # 1 dimension dp
        n = len(stones)
        dp = [0] * n
        stones = [0] + stones
        for i in range(n):
            stones[i + 1] += stones[i]
        for step in range(1, n):
            for i in range(n - step):
                dp[i] = max(stones[i + 1 + step] - stones[i + 1] - dp[i + 1], 
                            stones[i + step] - stones[i] - dp[i])
        return dp[0]