Python DP solution O(n) space and time.

  • 0

    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)]
                 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.