Elif statement breaks dynamic programming

jbuddy_13 0
Viewed 46

This is the Robber problem where a thief cannot steal from two adjacent homes but wants to maximize loot.

Example: input: arr = [2, 10, 3, 6, 8, 1, 7] output: 25 explanation: The greatest amount of money that a robber can get is 25, by the stealing the house 1, 4, and 6 (arr[1]+arr[4]+arr[6] = 10+8+7 = 25)

This solution does work.

def rob(arr):
    arr = tuple(arr)
    memory = {} 
    
    def helper(i=0):
        if i >= len(arr):
            return 0 
            
        if i not in memory:
            steal = arr[i] + helper(i+2)
            skip = helper(i+1)
            memory[i] = max(steal, skip)
        
        return memory[i]
    
    return helper()

But this solution returns 0.

def rob(arr):
    arr = tuple(arr)
    memory = {} 
    
    def helper(i=0):
        if i >= len(arr):
            return 0 
        
        elif memory[i]:
            return memory[i]
            
        else:
            steal = arr[i] + helper(i+2)
            skip = helper(i+1)
            memory[i] = max(steal, skip)
            return memory[i]
    
    return helper()

The key difference is the presence of the elif statement. Frankly, I don't understand how there is a difference in control flow. I believe these to be synonymous and should execute the same. However, this is not the case.

Could someone explain?

dynamic-programming python
1 Answers

I wasn't able to get the second block of code working when I tried to create an instance of Rob. It would seem that your elif condition is the problem. Try this, which works with a result of 25. I will try to explain how I thought through this below.

def rob(arr):
    arr = tuple(arr)
    memory = {} 
    
    def helper(i=0):
        if i >= len(arr):
            return 0 
        
        # elif memory[i]:
        #     return memory[i]
            
        else:
            steal = arr[i] + helper(i+2)
            skip = helper(i+1)
            memory[i] = max(steal, skip)
            return memory[i]
    
    return helper()

make_it_so = rob([2, 10, 3, 6, 8, 1, 7])
print(make_it_so)

So, if we uncomment the above code and try to create an instance of Rob - we see an error result which isn't really helpful. Why? Well, let's pre-add some data to your set as such:

def rob(arr):
    arr = tuple(arr)
    memory = {1} 
    
    def helper(i=0):
        if i >= len(arr):
            return 0 
        
        # elif memory[i]:
        #     return memory[i]
            
        else:
            steal = arr[i] + helper(i+2)
            skip = helper(i+1)
            memory[i] = max(steal, skip)
            return memory[i]
    
    return helper()

make_it_so = rob([2, 10, 3, 6, 8, 1, 7])
print(make_it_so)

Now our result is an error which is more clear - and helps us think about the problem. The error I see is "TypeError: 'set' object is not subscriptable". So then I think, what if we were to change your set to a list?

def rob(arr):
    arr = tuple(arr)
    memory = [1] 
    
    def helper(i=0):
        if i >= len(arr):
            return 0 
        
        elif memory[i]:
            return memory[i]
            
        else:
            steal = arr[i] + helper(i+2)
            skip = helper(i+1)
            memory[i] = max(steal, skip)
            return memory[i]
    
    return helper()

make_it_so = rob([2, 10, 3, 6, 8, 1, 7])
print(make_it_so)

Now our result is 1. This indicates to me, that the elif condition is being met, because it's returning position zero for a result of 1. Why? I think it's because you're asking program whether memory[i] is or isn't, and since you've previously created the empty set, and set to i=0, I believe it returns a true and then executes the instructions within that condition.

(Apologies, this is my first stackoverflow post and I'm not quite sure how to format well, or if I've even answered this correctly... hope it helps.)

Ira Bell0
Related