Question

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

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 a security system 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 = [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: 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 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Algorithm

This is a follow-up problem of problem 198-House-Robber, 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 determine the status of each house, it’s not sufficient to consider only whether the current house is being robbed. The statuses of the first and last houses should also be taken into account. To accomplish this, four columns are utilized.
Columns 0 and 1 indicate the statuses in which the last house is guaranteed not to be robbed, allowing the first house to be robbed without considering the last house. Columns 2 and 3 indicate the statuses in which the first house is guaranteed not to be robbed, allowing the last house to be robbed without considering the first house. Columns 0 and 2 represent the statuses in which the current house is not being robbed, while columns 1 and 3 represent the statuses in which the current house is being robbed.

The dynamic programming array represents the maximum amount of money that can be stolen up to the current house. For the first house at index 0, column 0 is always 0, column 1 is the amount of money in the house, and columns 2 and 3 are both 0 (since for columns 2 and 3, the first house is guaranteed not to be robbed). For the subsequent houses, column 0 is the maximum value of columns 0 and 1 in the previous row, column 1 is the sum of column 0 of the previous row and the amount of money in the current house, column 2 is the maximum value of columns 2 and 3 in the previous row, and column 3 is the sum of column 2 of the previous row and the amount of money in the current house.

Since the last house is guaranteed not to be robbed for columns 0 and 1, the values in column 0 and 1 of the last row should be set to those of the second last row.

The maximum value in the last row of the dynamic programming array represents the maximum amount of money that can be robbed.

Code

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;
        }
    }
}

############

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int s1 = robRange(nums, 0, n - 2);
        int s2 = robRange(nums, 1, n - 1);
        return Math.max(s1, s2);
    }

    private int robRange(int[] nums, int l, int r) {
        int a = 0, b = nums[l];
        for (int i = l + 1; i <= r; ++i) {
            int c = Math.max(nums[i] + a, b);
            a = b;
            b = c;
        }
        return b;
    }
}

// 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:
    def rob(self, nums: List[int]) -> int:
        def robRange(nums, l, r): # re-use LC-198 solution
            not_rob, rob = 0, nums[l]
            for num in nums[l + 1 : r + 1]: # to include 'r'
                not_rob, rob = rob, max(num + not_rob, rob)
            return rob

        n = len(nums)
        if n == 1:
            return nums[0]
        s1, s2 = robRange(nums, 0, n - 2), robRange(nums, 1, n - 1) # inclusive
        return max(s1, s2)

############

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

func rob(nums []int) int {
	n := len(nums)
	if n == 1 {
		return nums[0]
	}
	s1, s2 := robRange(nums, 0, n-2), robRange(nums, 1, n-1)
	return max(s1, s2)
}

func robRange(nums []int, l, r int) int {
	a, b := 0, nums[l]
	for i := l + 1; i <= r; i++ {
		a, b = b, max(nums[i]+a, b)
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

function rob(nums: number[]): number {
    const n = nums.length;
    if (n === 1) {
        return nums[0];
    }
    const robRange = (left: number, right: number) => {
        const dp = [0, 0];
        for (let i = left; i < right; i++) {
            [dp[0], dp[1]] = [dp[1], Math.max(dp[1], dp[0] + nums[i])];
        }
        return dp[1];
    };
    return Math.max(robRange(0, n - 1), robRange(1, n));
}

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n == 1 {
            return nums[0];
        }
        let rob_range = |left, right| {
            let mut dp = [0, 0];
            for i in left..right {
                dp = [dp[1], dp[1].max(dp[0] + nums[i])];
            }
            dp[1]
        };
        rob_range(0, n - 1).max(rob_range(1, n))
    }
}

213 - House Robber II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions