https://leetcode.com/problems/house-robber

Nice and easy dynamic programming problem! Let dp1 be maximum gain we can get, using last i-1 houses and dp2 maximum gain we can get, using i houses. How we need to update these numbers if we go from i to i+1? So dp1 and dp2 should mean gain for i and i+1 houses.

  1. dp1 = dp2, gain to rob i+1-1 houses is gain to rob i houses.
  2. dp2 = max(dp1 + num, dp2): we have 2 choices: either rob house number i+1, then we can rob ith house, so we have total gain dp1 + num, or we do not rob i+1th house, then we can gain dp2.

Complexity: time complexity is O(n), space complexity is O(1).

class Solution:
    def rob(self, nums):
        dp1, dp2 = 0, 0
        for num in nums:
            dp1, dp2 = dp2, max(dp1 + num, dp2)          
        return dp2

If you like the solution, you can upvote it on leetcode discussion section: Problem 0198