Python with memorization [48 ms]


  • 2
    class Solution(object):
        def PredictTheWinner(self, nums):
            def check(left, right, memo):
                if left > right:
                    return 0
                if left == right:
                    return nums[left]
                if not (left, right) in memo:
                    ss = sum(nums[left: right + 1])
                    l, r = ss - check(left + 1, right, memo) + nums[left], ss - check(left, right - 1, memo) + nums[right]
                    memo[(left, right)] = max(l, r)
                return memo[(left, right)]
    
            s = sum(nums)
            c1 = check(0, len(nums) - 1, {})
            return c1 >= s - c1
    

  • 0
    B

    Why is the summation necessary? Is it your style or something necessary?

    Thx!


  • 0
    B
    This post is deleted!

  • 3
    B
    class Solution(object):
        def PredictTheWinner(self, nums):
            def check(left, right, memo, depth=0):
                if left > right:
                    return 0
                if left == right:
                    return nums[left]
                if not (left, right) in memo:
                    # ss = sum(nums[left: right + 1])
                    # l, r = ss - check(left + 1, right, memo, depth+1) + nums[left], ss - check(left, right - 1, memo, depth+1) + nums[right]
                    l, r = - check(left + 1, right, memo, depth+1) + nums[left], - check(left, right - 1, memo, depth+1) + nums[right]
                    memo[(left, right)] = max(l, r)
                return memo[(left, right)]
    
            # s = sum(nums)
            c1 = check(0, len(nums) - 1, {})
            # return c1 >= s - c1
            return c1 >= 0
    

  • 1

    @bennykhoo99 No, I think summation is unnecessary, thanks for pointing it out.


  • 0
    H

    @bennykhoo99 Hi, may I ask what is the use of count 'depth'?


  • 0
    B

    @huayi5 it is remnant of the code to allow me to debug using print function :)


  • 0
    P
    l = ss - check(left + 1, right, memo, depth+1) 
    r = ss - check(left, right - 1, memo, depth+1) 
    

    It's strange that after removing the nums[left] or nums[right], still pass all the test cases.


Log in to reply
 

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