House Robber

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

Example

Given[3, 8, 4], return8.

Analysis

This is a typical DP problem. There is a template when solving a DP problem: state, function, initilization and answer.

state: dp[i], the maximum value a thief can steal in i houses.

function:

First establish the smallest state. And then start from the bigger state and iterate to the small state. The smallest state is there is one house, the robber will rob it. When there are two houses left, the thief will pick the one with the maximum money.

dp[2] = Math.max(dp[0] + value[2], dp[1]); so we can generate the function as f[i] = Math.max(f[i-2] + value[i] , f[i-1]).

initialization is dp[0] = value[0] and dp[1] = Math.max(value[0], value[1])

answer is dp[array.length-1]

Solution

 public long houseRobber(int[] A) {
    if (A == null || A.length == 0){
        return 0;
    }

    long[] dp = new long[A.length];
    for (int i = 0; i < A.length; i++){
        if (i ==  0){
            dp[0] = A[0];
        } else if (i == 1){
            dp[1] = Math.max(dp[0], A[1]);
        } else {
            dp[i] = Math.max(dp[i-2] + A[i], dp[i-1]);
        }
    }

    return dp[A.length-1];
}

solution with recursion (poor performance)

long[] dp = null;
public long houseRobber(int[] A) {
    if (A == null || A.length == 0){
        return 0;
    }

    dp = new long[A.length];
    helper(dp, A, A.length-1);
    return dp[A.length-1];
}

public long helper(long[] dp, int[] A, int i){
    if (i == 0) {
        dp[0] = A[0];
    } else if (i == 1) {
        dp[1] = Math.max(A[0], A[1]);
    } else {
        dp[i] = Math.max(helper(dp, A, i-2) + A[i], helper(dp, A, i-1));
    }

    return dp[i];
}

House Robber II

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

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.

Example

nums =[3,6,4], return6

Analysis

In this question, If the thief robs the first house, he can't rob the last house, vice versa. Therefore, two calculations should be carried out. One without the first house, and another without the last house, and then compare the two to get the best one.

Take away of this question is when a problem has a circular dependency and ask for the optimal solution. Try to break the circular dependency and carry out the calculation separately for each scenario, and compare the outcomes to get the optimal solution.

Solution

int[] dp = null; 

public int houseRobber2(int[] nums) {
    if (nums == null || nums.length == 0){
        return 0;
    }

    if (nums.length == 1){
        return nums[0];
    }

    if (nums.length == 2){
        return Math.max(nums[0], nums[1]);
    }

    dp = new int[nums.length];
    return Math.max(helper(nums, 0, nums.length - 1), helper(nums, 1, nums.length));
}

public int helper(int[] nums, int start, int end){
    if (start > end || nums.length < end){
        return 0;
    } 

    int[] dp = new int[nums.length];

    dp[start] = nums[start];
    dp[start+1] = Math.max(nums[start], nums[start+1]);

    for (int i = start + 2; i < end; i++){
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
    }

    return dp[end - 1];
}