Python DP solution O(n) space and time.


  • 0
    O

    Python recursive solution. If one forget to add a cache (The dictionary d in the following), the time complexity will be $O(2^n)$ and will give you TLE.

     def rob(self, nums):
            d = {}
            def DP(nums):
                 if not nums: return 0
                 if len(nums) in d: return d[len(nums)]
                 d[len(nums)]=max(nums[0]+DP(nums[2:]),DP(nums[1:]))            
                 return d[len(nums)]
            return DP(nums)
    

Log in to reply
 

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