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