Problem statement

https://binarysearch.com/problems/Candy-Race/

Solution

Equal to Leetcode 0877. Stone Game, but here we can have ties, because we can have even number of candies.

Complexity

It is O(n^2) time/space.

Code

class Solution:
    def solve(self, P):
        @lru_cache(None)
        def dp(i, j): 
            if i == j: return P[i]
            return max(P[i] - dp(i+1, j), P[j] - dp(i, j-1))
        
        return dp(0, len(P) - 1) > 0