[coding]
[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.