House Robber II

Posted on January 03, 2017 

  Code   Leetcode


升级版的House Robber,现在头尾成环,求最大可能的抢劫数量,不能相邻取。

Note: This is an extension of House Robber.

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.


参考House Robber中的动态规划解法。



public class Solution {
    public int rob(int[] nums) {
        if (nums.length <= 1) return nums.length == 0 ? 0 : nums[0];

        return Math.max(rob(nums, 0, nums.length - 1), rob(nums, 1, nums.length));
    private int rob(int[] nums, int left, int right) {
        int ans = 0;
        int pre = 0, hist = 0;
        for (int i = left; i < right; i++) {
            ans = Math.max(hist + nums[i], pre);
            hist = pre;
            pre = ans;
        return Math.max(ans, pre);