Python easy to understand solution


  • 1
    F

    Just use the memorization and keep moving forward. If it is at subarray (i, j) and for player 1 to move, then return either nums[i]+(i+1,j) or nums[j]+(i,j-1). And for player 2, he needs to minimize player 1's points, so just use min funciton instead. And if player 1's points is greater than player 2's points, which means player 1's points is greater than or equal to the sum of the total array, returns True. Fairly easy to understand.

    class Solution(object):
        def PredictTheWinner(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            def predict(start, end, turn):
                if cache[start][end] == -1:
                    r = 0
                    if start == end:
                        r = nums[start] if turn else 0
                    else:
                        if turn:
                            r = max(nums[start]+predict(start+1, end, False), nums[end]+predict(start, end-1, False))
                        else:
                            r = min(predict(start+1, end, True), predict(start, end-1, True))
                    cache[start][end] = r
                return cache[start][end]
            
            n = len(nums)
            cache = [[-1 for i in xrange(n)] for j in xrange(n)]
            return 2*predict(0, len(nums)-1, True) >= sum(nums)
    

  • 0
    J
    This post is deleted!

Log in to reply
 

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