dp by bfs+dfs in python


  • 0
    class Solution(object):
        def PredictTheWinner(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            cache={}
            dict3={}
            thre=sum(nums)/2.0
            if thre==0:return True
            def maximum(a,b):#[a,b)
                #print a,"@",b
                if (a,b) in cache:return cache[(a,b)]
                if a>=b:res=0
                elif a==b-1:res=nums[a]
                elif b-a==2:res=max(nums[a],nums[a+1])
                else :res=max(min(nums[a]+maximum(a+1,b-1),nums[a]+maximum(a+2,b)),min(nums[b-1]+maximum(a+1,b-1),nums[b-1]+maximum(a,b-2)))
                cache[(a,b)]=res
                #print cache
                return res
            for i in range(0,len(nums)-(len(nums)>>1)):
                maximum(i,i+(len(nums)>>1))
            if maximum(0,len(nums))>=thre:return True
            return False
    

Log in to reply
 

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