Problem statement

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

Solution

One solution is to use dp with state (i, t) where we have subproblem [i, end] and t = 1 for the turn of first and t = -1 for the turn of second.

Complexity

Complexity is O(n) but with quite big constant.

Code

class Solution:
    def stoneGameIII(self, A):
        @lru_cache(None)
        def dp(i, t):
            if i == n: return 0
            cands, last = [], 0
            for j in range(i, min(i+3, n)):
                last += A[j]*t
                cands.append(dp(j + 1, -t) + last)
            
            if t > 0: return max(cands)
            if t < 0: return min(cands)
        
        n = len(A)
        score = dp(0, 1)
        return "Tie" if score == 0 else "Alice" if score > 0 else "Bob"

Actually we can avoid second parameter, if we denote by dp maximum score we can get for the first person start with this index. Then There are three option for Alice to choose: take A[i], then gain is A[i] - dp[i+1], also we have option A[i] + A[i+1] - dp[i+1] and A[i] + A[i+1] + A[i+2] - dp[i+1] and we need to choose the best one.

Complexity

Is the same as previous but with smaller conatant.

Code 2

class Solution:
    def stoneGameIII(self, A):
        @lru_cache(None)
        def dp(i):
            if i == n: return 0
            ans, last = -float("inf"), 0
            for j in range(i, min(i+3, n)):
                last += A[j]
                ans = max(ans, last - dp(j + 1))
            return ans
            
        n = len(A)
        score = dp(0)
        return "Tie" if score == 0 else "Alice" if score > 0 else "Bob"