1690.md

1690. Stone Game VII

Solution 1 (time O(n^2), space O(n^2))

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