Question

Formatted question description: https://leetcode.ca/all/213.html

 213	House Robber II

 You are a professional robber planning to rob houses along a street.
 Each house has a certain amount of money stashed.

 All houses at this place are arranged in a circle.
 That means the first house is the neighbor of the last one.
 Meanwhile, 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:

 Input: [2,3,2]
 Output: 3
 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
 because they are adjacent houses.

 Example 2:

 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.

 @tag-dp

Algorithm

This is a follow-up problem of problem 198, and the difference between the two problems is that in this problem, the first house is the neighbor of the last one.

Similar to problem 198, this problem can also be solved using dynamic programming. However, since the first house and the last house are adjacent, the statuses should be represented differently.

The dynamic programming array consists of N rows and 4 columns, where N is the number of houses, and thus each row represents the statuses of each house.

  • To represent the statuses of each house, not only whether the current house is robbed should be considered, but whether the first house or the last house is robbed should also be considered, so 4 columns are used.
  • Column 0 and column 1 represent the statuses that the last house is guaranteed to not robbed so the first house can be robbed without considering the last house, and column 2 and column 3 represent the statuses that the first house is guaranteed not robbed so the last house can be robbed without considering the first house. Column 0 and column 2 represent the statuses that the current house is not robbed, and column 1 and column 3 represent the statuses that the current house is robbed.

The dynamic programming array represents the maximum amount of money to be robbed up to the current house.

For the house at index 0, obviously column 0 is 0, column 1 is the amount of money in the house, and column 2 and column 3 are both 0 (since for column 2 and column 3, the first house is guaranteed not to be robbed). For the following houses, column 0 is the max value of column 0 and column 1 of the previous row, column 1 equals column 0 of the previous row plus the amount of money in the current house, column 2 is the max value of column 2 and column 3 of the previous row, and column 3 equals column 2 of the previous row plus the amount of money in the current house.

Since for column 0 and column 1, the last house is guaranteed to not be robbed, set column 0 and column 1 of the last row to be equal to column 0 and column 1 of the second last row.

Then the max value of the last row of the dynamic programming array is the maximum amount of money that can be robbed.

Code

Java

  • public class House_Robber_II {
    
        class Solution_optimize {
            public int rob(int[] nums) {
                if (nums == null || nums.length == 0) {
                    return 0;
                }
                if (nums.length == 1) {
                    return nums[0];
                }
    
                return Math.max(rob(nums, 0, nums.length - 1), rob(nums, 1, nums.length));
            }
    
            // right exclusive
            private int rob(int[] nums, int left, int right) {
                int odd = 0;
                int even = 0;
    
                for (int i = left; i < right; i++) {
                    if (i % 2 == 0) { // @note: also working: if (i % 2 == 1) {
                        even = Math.max(even + nums[i], odd); // 上次even,这次下一个even
                    } else {
                        odd = Math.max(odd + nums[i], even); // 上次odd,这次下一个odd
                    }
                }
    
                return Math.max(even, odd);
            }
        }
    
    
        public class Solution {
            public int rob(int[] nums) {
                if (nums == null || nums.length == 0) {
                    return 0;
                }
    
                if (nums.length == 1) {
                    return nums[0];
                }
    
                int n = nums.length;
                // case-1: Rob the first house, not the last one.
                int[] dp = new int[n + 1];
                dp[0] = 0;
                dp[1] = nums[0];
    
                for (int i = 2; i < n; i++) {
                    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
                }
    
                dp[n] = dp[n - 1]; // not robbing last one
    
                // case-2: Not rob the first, might or may not rob  the last one
                int[] dp2 = new int[n + 1];
                dp2[0] = 0;
                dp2[1] = 0;
    
                for (int i = 2; i < n + 1; i++) {
                    dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i - 1]);
                }
    
                return Math.max(dp[n], dp2[n]);
            }
        }
    
        class Solution_2Ddp {
            public int rob(int[] nums) {
                if (nums == null || nums.length == 0)
                    return 0;
                int length = nums.length;
                if (length == 1)
                    return nums[0];
                int[][] dp = new int[length][4];
                dp[0][0] = 0;
                dp[0][1] = nums[0];
                dp[0][2] = 0;
                dp[0][3] = 0;
                for (int i = 1; i < length; i++) {
                    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
                    dp[i][1] = dp[i - 1][0] + nums[i];
                    dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][3]);
                    dp[i][3] = dp[i - 1][2] + nums[i];
                }
                for (int i = 0; i < 2; i++)
                    dp[length - 1][i] = dp[length - 2][i];
                return max(dp[length - 1]);
            }
    
            public int max(int[] array) {
                int max = Integer.MIN_VALUE;
                for (int num : array)
                    max = Math.max(max, num);
                return max;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/house-robber-ii/
    // Time: O(N)
    // Space: O(1)
    class Solution {
        int rob(vector<int>& A, int start, int end) {
            if (start == end) return 0;
            if (start + 1 == end) return A[start];
            int prev2 = 0, prev = 0;
            for (int i = start; i < end; ++i) {
                int cur = max(prev, A[i] + prev2);
                prev2 = prev;
                prev = cur;
            }
            return prev;
        }
    public:
        int rob(vector<int>& A) {
            if (A.size() == 1) return A[0];
            return max(rob(A, 1, A.size()), rob(A, 0, A.size() - 1));
        }
    };
    
  • class Solution(object):
      def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0 or nums is None:
          return 0
        if len(nums) <= 2:
          return max(nums[:])
        # If we rob the first house, the problem becomes how to rob houses except the last one.
        # If we rob the last house, the problem becomes how to rob houses ecept the first one.
        return max(self.robHelper(nums[1:]), self.robHelper(nums[:len(nums) - 1]))
    
      def robHelper(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        pp = nums[0]
        p = max(pp, nums[1])
        for i in range(2, len(nums)):
          tmp = p
          p = max(pp + nums[i], p)
          pp = tmp
        return p
    
    

All Problems

All Solutions