How to approach most of DP problems (House Robber)

This particular problem and most of others can be approached using the following sequence :

1. Find recursive relation

2. Recursive (top-down)

3. Recursive + memo (top-down)

4. Iterative + memo (bottom-up)

5. Iterative + N variables (bottom-up)

Step 1. Figure out recursive relation.

A robber has 2 options : 1) rob current house i; 2) don't rob current house.

If an option "a" is selected it means she can't rob previous i-1 house but can safely proceed to the one before previous i-2 and gets all cumulative loot that follows. 

If an option "b" is selected the robber gets all the possible loot from robbery of i-1 and all the following buildings.

So it boils down to caculating what is more profitable :

•robbery of current house + loot from houses before the previous

•loot from the previous house robbery and any loot captured before that

rob(i) = max(rob(i-2) + currentHouseValue, rob(i-1))

Step 2. Recursive (top-down)

Converting the recurrent relation from step1 shouldn't be very hard.

def rob(nums, i) :
 
    if i < 0 :
        return 0
 
    return max(rob(nums, i-2) + nums[i], rob(nums, i-1))

This algorithm will process the same i multiple times and it needs improvement.

Step 3. Recursive + memo (top-down)

memo = []
 
def solve(nums) :
 
    memo = [-1]*len(nums)
    return rob(nums, len(nums)-1)
 
def rob(nums, i) :
 
    if i < 0 :
        return 0
 
    if memo[i] >= 0 :
        return memo[i]
 
    memo[i] = max(rob(nums, i-2) + nums[i], rob(nums, i-1))
    return memo[i]

Much better, this should run in O(n) time. Space complexity is O(n) as well, because of the recursion stack, let's try to get rid of it.

Step 4. Iterative + memo (bottom-up)

def rob (nums) :
 
    if len(nums) == 0 :
        return 0
    
    memo = [-1]*len(nums)
 
    memo[0] = 0
    memo[1] = nums[0]
 
    for i in range(1, len(nums)) :
        val = nums[i]
        memo[i+1] = max(memo[i], memo[i-1]+val)
 
    return memo[-1]
 

Step 5. Iterative + 2 variables (bottom-up)

We can notice that in the previous step we use only memo[i] and memo[i-1], so going just 2 step back. We can hold them in 2 variables instead. This optimization is met in Fibonacci sequence creation and some other problems [to paste links].

def rob (nums) :
    
    if not nums :
        return 0
 
    prev1, prev2 = 0, 0
 
    for num in nums :
        tmp = prev1
        prev1 = max(prev2 + num, prev1)
        prev2 = tmp
 
    return prev1

Source :

https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/576/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems./235329