Question: https://leetcode.com/problems/house-robber/
Question Name: House Robber
Simple DP problem. If you want, you could improve the space complexity to O(1) with bookkeeping (the second previous house, the previous house, and the current house).
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: # @param {integer[]} nums # @return {integer} def rob(self, nums): if len(nums) == 0: return 0 if len(nums) <= 2: return max(nums) max_money = [0] * len(nums) max_money[0] = nums[0] max_money[1] = max(nums[0], nums[1]) for house in xrange(2, len(nums)): max_money[house] = max(max_money[house-1], max_money[house-2]+nums[house]) return max_money[-1] |