Python codes with comments

  • 0

    Typical DP idea, from bottom to top

    class Solution(object):
        def PredictTheWinner(self, nums):
            :type nums: List[int]
            :rtype: bool
            L = len(nums)
            if L<=2:
                return True
            # each cell in L*L matrix is [player 1 score, player 2 score]
            dp = [[[0, 0] for _ in range(L)] for __ in range(L)] 
            for dis in range(1, L):
                for i in range(0, L-dis):
                    j = i+dis
                    # Compute dp[i][j] based on dp[i+1][j] and dp[i][j-1].
                    # player 1 select nums[i]
                    a1, b1 = nums[i]+dp[i+1][j][1], dp[i+1][j][0]
                    # player 1 select nums[j]
                    a2, b2 = nums[j]+dp[i][j-1][1], dp[i][j-1][0]
                    if a1>a2:
                        dp[i][j][0], dp[i][j][1] = a1, b1
                        dp[i][j][0], dp[i][j][1] = a2, b2
            return dp[0][-1][0]>=dp[0][-1][1]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.