Predict the Winner

Problem Id: 486 Difficulty: Medium


Intuition

Solution


class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        """
        DP problem

        play2[i][j] = min(play1[i][j-1], play1[i+1][j])
        play1[i][j] = max(play2[i][j-1] + nums[j], play2[i+1][j] + nums[i])

        play1[0][-1] > sum(nums) // 2
        """
        # Edge cases
        if not nums:
            return True

        # Prepare
        n = len(nums)
        if n % 2 == 1:
            win = 1
        else:
            win = 2
        dp = [[0] * n for _ in range(n)]
        lo = 0
        while lo + win <= n:
            hi = lo + win - 1
            dp[lo][hi] = max(nums[lo:hi + 1])
            lo += 1

        # DP alg
        while win < n:
            win += 1
            lo = 0
            while lo + win <= n:
                hi = lo + win - 1
                dp[lo][hi] = min(dp[lo][hi - 1], dp[lo + 1][hi])
                lo += 1
            win += 1
            lo = 0
            while lo + win <= n:
                hi = lo + win - 1
                dp[lo][hi] = max(
                    dp[lo][hi - 1] + nums[hi],
                    dp[lo + 1][hi] + nums[lo]
                )
                lo += 1
        return dp[0][-1] >= sum(nums) / 2