[LC877] Stone Game

First try, but not optimal solution. 30 min time. I used a dp state of dp[i][j][player] to keep track of the state where the state is the maximum number of stones that "player" can get using only the stones from i to j. In this way, we maintain state for both players. This works, but is not the optimal dp setup. I needed to ask myself the question: What state would be sufficient to know who wins? Well we just need to maintain the difference between the two players. So at each step -- regardless of whose turn it is -- our state should be dp[i][j] = the maximum advantage the current player has over the opponent. My solution which maintains two states is below.

1class Solution(object):
2    def stoneGame(self, piles):
3        """
4        :type piles: List[int]
5        :rtype: bool
6        """
7        n = len(piles)
8        dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
9
10        for i in range(n):
11            dp[i][i] = (0, piles[i])
12
13        for k in range(2, n+1):
14            for i in range(0, n-k+1):
15                j=i+k-1
16
17                if k % 2 == 0:
18                    dp[i][j][0] = (max(piles[i] + dp[i+1][j][0], piles[j]+ dp[i][j-1][0]),dp[i][j][1])
19                if k % 2 == 1:
20                    dp[i][j][1] = (dp[i][j][0], max(piles[i] + dp[i+1][j][1], piles[j] + dp[i][j-1][1]))
21        if dp[0][n-1][0] > dp[0][n-1][1]:
22            return True
23        return False