Issue with memoization - House Robber problem

Question

I have a recursive solution that works, but it turns out a lot of subproblems are being recalculated. I need help with MEMOIZATION.

So here's the problem statement:

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Examples:

Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

Another one:

Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

And another one

Input: [2, 1, 1, 2] Output: 4 Explanation: Rob house 1 (money = 2) and then rob house 4 (money = 2). Total amount you can rob = 2 + 2 = 4.

Now like I said I have a perfectly working recursive solution: When I build a recursive solution. I don't THINK too much. I just try to understand what the smaller subproblems are.

option_1: I add the value in my current index, and go to index + 2

option_2: I don't add the value in my current index, and I search starting from index + 1 Maximum amount of money = max(option_1, option_2)

money = [1, 2, 1, 1] #Amounts that can be looted


def helper(value, index):

    if index >= len(money):

        return value

    else:
        option1 = value + money[index]
        new_index1 = index + 2

        option2 = value
        new_index2 = index + 1

        return max(helper(option1, new_index1), helper(option2, new_index2))



helper(0, 0) #Starting of at value = 0 and index = 0

This works perfectly.. and returns the correct value 3.

I then try my hand at MEMOIZING.

money = [1, 2, 1, 1]

max_dict = {}
def helper(value, index):

    if index in max_dict:
        return max_dict[index]

    elif index >= len(l1):

        return value

    else:
        option1 = value + money[index]
        new_index1 = index + 2

        option2 = value
        new_index2 = index + 1

        max_dict[index] = max(helper(option1, new_index1), helper(option2, new_index2))

        return max_dict[index]


helper(0, 0)

I simply have a dictionary called max_dict that STORES the value, and each recursive call checks if the value already exists and then accordingly grabs it and prints it out..

But I get the wrong solution for this as 2 instead of 3. I went to pythontutor.com and typed my solution out, but I can't seem to get the recursion tree and where it's failing..

Could someone give me a correct implementation of memoization while keeping the overall structure the same? In other words, I don't want the recursive function definition to change

Answer 1

Your approach for memoization won't work because when you reach some index i, if you've already computed some result for i, your algorithm fails to consider the fact that there might be a better result available by robbing a more optimal set of houses in the left portion of the array.

The solution to this dilemma is to avoid passing the running value (money you've robbed) downward through the recursive calls from parents to children. The idea is to compute sub-problem results without any input from ancestor nodes, then build the larger solutions from the smaller ones on the way back up the call stack.

Memoization of index i will then work because a given index i will always have a unique set of subproblems whose solutions will not be corrupted by choices from ancestors in the left portion of the array. This preserves the optimal substructure that's necessary for DP to work.

Additionally, I recommend avoiding global variables in favor of passing your data directly into the function.

def maximize_robberies(houses, memo, i=0):
    if i in memo:
        return memo[i]
    elif i >= len(houses):
        return 0

    memo[i] = max(
        maximize_robberies(houses, memo, i + 1),
        maximize_robberies(houses, memo, i + 2) + houses[i],
    )
    return memo[i]

if __name__ == "__main__":
    print(maximize_robberies([1, 2, 1, 1], {}))

Answer 2

I solved this dynamic programming problem using below method. And it is happenning in O(n) time. Do try this.

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def rob(self, nums):
            n = len(nums)
            if n==0:
                return 0;
            if n == 1:
                return nums[0]
            s = [0]*(n+1)
            s[1] = nums[0]
            s[2] = nums[1]

            for i in range(3,n+1):
                s[i] = (max(s[i-2],s[i-3]) + nums[i-1])
            return max(s[n],s[n-1])


    money = [2, 1, 1, 2]
    sol = Solution()
    print(sol.rob(money))