House Robber : Part 1

Problem 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 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.

Solutions

This problem is a typical dynamic programming problem. Here I just want to explain a little bit for those who are at the beginning of the long journey - programming every day! (For those who are familiar with DP, you can take a look at some solutions below, they might be useful for you ^_^.)

In dynamic programming problem, all we need to do is to find the recursion function. In many difficult problems, it is very hard to find the recursion functions. However, in this problem, it is pretty easy.

All you need to think is: which function we should choose in this problem? 

A typical thinking when encountering this problem is: we have some f(n) if array is of length n. How f(n+1) is calculated if array is of length (n+1)?

suppose the array is of length n, and the maximum amount of money you can rob is f(n). We need to make another condition here: we must rob the last house in that array! Why do we need this? To make it easy to calculate the function recursively. Yes it is.

I will list the recursion relation here, and you will think why:

f(n+3) = A[n+3] + max ( f(n+1) , f(n)) , where A is 1-based array of amounts of money you can rob.

And we can put this into code in java & python as below

I. Java

public class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n > 2)
            nums[2] += nums[0];
        for (int i = 3; i<nums.length; i++){
            nums[i] += Math.max(nums[i-2], nums[i-3]);
        }
        return Math.max(nums[n-1], nums[n-2]);
    }   
}

II. Python

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]
        if n > 2:
            nums[2] += nums[0]
        for i in range(3, n):
            nums[i] += max(nums[i-2], nums[i-3])
            
        return max(nums[n-1], nums[n-2])

III. Python - 3 line version
You might not satisfied with the above the solutions. But thhe following code is too simple that makes me fall in love with python forever!

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        first, second = 0, 0
        for i in nums: first, second = second, max(first + i, second)
        return second

NOTE: the above code is based on the following formula:

f(0) = nums[0]
f(1) = max(nums[0], nums[1])
f(k) = max( f(k-2) + nums[k], f(k-1) )

IV. Java version of the 3-line python version

public class Solution {

    public int rob(int[] num) {
        int first = 0; int second = 0; int t;
        for (int n :num) {
            t = second;
            second = Math.max(first + n, second);
            first = t;
        }
        return second;        
    }
}