23.07.28 Today’s Leetcode

486. Predict the Winner (medium)

DFS Approach

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True

        def dfs(i, j):
            if i > j:
                return math.inf
            if i == j:
                return nums[i]
            temp = max(nums[i] - dfs(i + 1, j), nums[j] - dfs(i, j - 1))
            return temp

        p = dfs(0, len(nums) - 1)
        print(p)
        return p >= 0

DP Solution

class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = nums[:]
        for diff in range(1, n): 
            for left in range(n - diff): 
                right = left + diff
                dp[left] = max(nums[left] - dp[left + 1], nums[right] - dp[left])
        return dp[0] >= 0