[LeetCode] 198. House Robber

Posted on | In

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

Example 1:

1
2
3
4
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.

Example 2:

1
2
3
4
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.

Explanation 1

  1. We can use dynamic programming to solve this problem.

  2. Dynamic state is creating a one dimensional array dp. dp[i] means the total maximum money when rob start from the first house to the index i house.

  3. Dynamic init. For example if nums = [3, 2, 1, 5], then in index0 dp[0] = 3; then in index1, dp[1] = 3 because 3 > 2.

  4. Dyamic function. In index2, because we cannot rob the adjancent houses, so if we rob the current index2 house, then we cannot rob index1 house, in other word, if we rob index2, then dp[2] = dp[0] + nums[2]; if we don’t rob index2 house, then dp[2] = dp[1]; so we can take the maximum of rob or not rob, which is max(dp[0]+nums[2], dp[1]). Therefore, dynamic function is dp[i] = max(dp[i-2] + nums[i], dp[i-1]).

  5. Dynamic result is returning the last index of dp.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int rob(int[] nums) {
        if (nums.length <= 1) return nums.length == 0 ? 0 : nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);

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

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

        return dp[nums.length - 1];
    }
}

Explanation 2

  1. We can save space by using four variables rob, notRob, preRob, preNotRob.

  2. rob and notRob means the current index house, we rob or notRob.

  3. preRob and preNotRob means the at previous index house, we rob or notRob.

  4. If we rob the current index house, then we cannot rob the previous index house, which means rob = nums[i] + preNotRob.

  5. If we do not rob the current index house, then we can either rob the previous index house or don’t rob the previous hosue. We will take the maximum of these two.

  6. In each iteration, we calculate rob and notRob. At the end of the iteration, we return the maximum of rob and notRob.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int rob(int[] nums) {
        int rob = 0, notRob = 0;

        for (int i = 0; i < nums.length; i++) {
            int preRob = rob, preNotRob = notRob;
            rob = nums[i] + preNotRob;
            notRob = Math.max(preRob, preNotRob);
        }

        return Math.max(rob, notRob);
    }
}