CODEWITHSUNDEEP
algorithmdynamic-programmingmemoization
Niko
Niko

Reputation: 810

House Robber Memoization

This is a question regarding the memoization approach on leetcode's problem House Robber. Here you may find the actual description of the problem.

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Input: nums = [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.

The following is the top voted answer using memoization on leetcode

    int rob(int[] nums) {
        int[] memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return doRob(nums, 0, memo);
    }

    private int doRob(int[] nums, int index, int[] memo) {
        if (index >= nums.length) return 0;
        if (memo[index] == -1)
            memo[index] = Math.max(nums[index] + doRob(nums, index + 2, memo), doRob(nums, index + 1, memo));
        return memo[index];
    }

as you can see we have two options on every iteration

  1. Either rob the house and continue to the next non adjacent one
  2. Do not rob the house the continue to the adjacent one

To improve the time complexity on this we have a memoization array that carries the max loot starting from every house - at least this is what the solution claims.

I do not understand the following: If we decide to not rob house i and down this path we realize that doRob(nums, i + 2) + nums[i] < doRob(nums, i + 1). So in other words we realize that the path taken when we decided to not rob house i produces a higher loot than the path taken after do robbing the house. Then we would set memo[i] = doRob(nums, i + 1). So we are assigning the max loot starting from index i to the loot produced by a path that does not include house i. Is this right? It does not seem right to me.

Upvotes: 1

Views: 744

Answers (1)

CiaPan
CiaPan

Reputation: 9570

Yes, your understanding of the code is correct, and yes, the code is right.

The code actually works backwards and calculates possible highest loots from the end of the street deep in the recursion towards its beginning on successive returns.

Suppose a 'street' with money available 1,7,2,... and consider the simpler algorithm that works forward, without unnecessary recursion.

Then the maximum loot possible on the three-house initial segment is 7, which indeed does not include money from the third house. This is because the thief is not obliged to enter every other house.

As an example, for input like 1,7,2,1,10,1 robbering either the third or the fourth house will exclude 7 or 10, hence decrease the final result. So, when we consider the 5-th house with 10 we need to account for 7 from first three houses, even though it does not include money from the third house.

Upvotes: 1

Related Questions