Leetcode 486 Solution

This article provides solution to leetcode question 486 (predict-the-winner).
Categories:
Tags:
Access this page by simply typing in "lcs 486" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/predict-the-winner

Solution

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        m = {}
        
        def predict(i, j):
            nonlocal nums

            if i == j:
                return nums[i]
            
            key = (i, j)
            
            if key in m:
                return m[key]
            
            res = max(
                nums[i] - predict(i + 1, j),
                nums[j] - predict(i, j - 1),
            )
            
            m[key] = res
            return res

        return predict(0, len(nums) - 1) >= 0