Problem statement

https://leetcode.com/problems/stone-game-vii/

Solution

We can see dynamic programming structure in this problem: each time we take some stones from the left or from the left side, what is rest is always contigious array. So, let us denote by dp(i, j) the biggest difference in scores for the person who start with this position.

  1. If i > j, then we have empty array and result is zero.
  2. In the opposite case, we have two options: we can take either leftmost stone or rightmost stone. We also precomputed CSum: cumulative sums to evaluate sums in ranges in O(1) time. We can either can gain sum from [i+1, j] and subtract dp(i+1, j) or we can gain sum from [i, j-1] and subtract dp(i, j-1). Why we need to subtract here? Because dp(i+1, j) and dp(i, j-1) is maximum difference of scores another player can gain, so for current player we need to take negative value.

Complexity

We have O(n^2) states with 2 transactions from every state, so total time and space is O(n^2).

Code

class Solution:
    def stoneGameVII(self, A):
        CSum = [0] + list(accumulate(A))
        @lru_cache(2000)
        def dp(i, j):
            if i > j: return 0
            sm = CSum[j + 1] - CSum[i]
            return sm - min(A[i] + dp(i+1, j), A[j] + dp(i, j-1))
        
        return dp(0, len(A) - 1)

Important remark

Sometimes when we use lru_cache, it works slower than memoisation by hands, and in this problem you will get TLE if you use usual @lru_cache(None), because restrictions in this problem are quite tight on python. So, what you can do during contest to avoid this?

  1. Do memorisation by hands: it is the quickest and working way to do it: instead of lru_cache, use say dictionary d and each time in the beginning check if we have element in d or not.
  2. Change None in lru_cache to some magical constant, here 1000 to 10000 will work fine, but I do not have explanation why. And on the contest you can not be lucky to get it or you get it and then it will be rejudged and you will get TLE or MLE. So, it is not safe in my opinion.
  3. Use classical table dp, where you have here 2d list of lists and then fill it with usual ways. It is also safe way, but I am so used to lru_cache, so for this one I would have spend more time on contest, but if method 1 is not working, you should definitely go to this one.