House Robber

Description:

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.

Example 1:

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.

Example 2:

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

Solution:

Oh my God, that is Dynamic programming. I can’t believe that I’ve solved a dynamic programming problem.

Looks like we cannot use a greedy approach because, for example in array [3 5 3] result should be six instead of five.

That is why we need another algorithm. I must have spent much time on this problem, but nope.

In dynamic programming, you must always find the base function.

In our case

f(n) = Largest amount that you can rob from the first house to nth indexed house.

Ai = Amount of money at the ith index house.

At each house, we have the choice of robbing it or leaving it.

In the first case:

if we pick the last house:
then,we can’t pick (n-1)th house, hence f(n)= An + f(n-2)

In the second case:

if we leave last house:
then, we will stick with the max profit till (n-1)th house, hencef(n)= f(n-1)

Let us see base cases.
n = 0, clearly f(0) = A0.
n = 1, then f(1) = max(A0, A1).

Hence we can summarize the formula as following :
f(n)= max( An + f(n-2) , f(n-1) )

You may have thought that we need smth else, hah me too, but that is it.

I must have thought that dynamic problems have an insane level. After this one, I don’t think so.

Let’s code it:

public int rob(int[] nums) {
    if (nums == null){
        return 0;
    }
    if (nums.length == 1){
        return nums[0];
    }
    int[] rob = new int[nums.length];
    rob[0] = nums[0];
    rob[1] = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++){
        int curAndPrev = nums[i] + rob[i-2];
        rob[i] = Math.max(curAndPrev, rob[i-1]);
    }
    return rob[rob.length-1];
}

Write comments and share your reactions. Peace.