Using problem 198 modify a little, DP Python code


  • 0
    W
    class Solution(object):
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n=len(nums)
            
            if len(nums)==0:
                return 0
            elif len(nums)==1:
                return nums[0]
            elif len(nums)==2:
                return max(nums)
            return max(self.robx(nums[0:n-1]),self.robx(nums[1:n]))
            
        def robx(self, nums):
            if len(nums)==0:
                return 0
            elif len(nums)==1:
                return nums[0]
            elif len(nums)==2:
                return max(nums)
            a=nums[0]
            b=max(nums[0],nums[1])
            for i in range(2,len(nums)):
                a,b=b,max(a+nums[i],b)
            return b
    

    robx(nums) is code for problem 198, for circle case, only consider if nums[0] is chosen, nums[n-1] would not be chosen, so is nums[0:n-1]; if nums[0] has not been chosen, nums[n-1] could be chosen, so is nums[1:n].


Log in to reply
 

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