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.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

198. House Robber 的拓展，现在房子排成了一个圆圈，抢第一个屋子就不能抢最后一个屋子，抢最后一个屋子就不能抢第一个屋子。

解法：还是动态规划DP，分别算出这两个条件下的最大抢劫金额，然后取更大的就行。

Java:

public class Solution {

    public int rob(int[] nums) {

        return Math.max(rob(nums, 0), rob(nums, 1));

    }

    public int rob(int[] nums, int offset) {

        // 如果长度过小，则直接返回结果

        if(nums.length <= 1 + offset){

            return nums.length <= offset ? 0 : nums[0 + offset];

        }

        int a = nums[0 + offset];

        // 如果offset是1，则从下标为1的元素开始计算，所以要比较nums[1]和nums[2]

        int b = Math.max(nums[0 + offset], nums[1 + offset]);

        // 对于不抢劫最后一个房子的情况，i要小于nums.length - 1

        for(int i = 2 + offset; i < nums.length - 1 + offset; i++){

            int tmp = b;

            b = Math.max(a + nums[i], b);

            a = tmp;

        }

        return b;

    }

}

Python:

class Solution:

    # @param {integer[]} nums

    # @return {integer}

    def rob(self, nums):

        if len(nums) == 0:

            return 0

        if len(nums) == 1:

            return nums[0]

        return max(self.robRange(nums, 0, len(nums) - 1),\

                   self.robRange(nums, 1, len(nums)))

    def robRange(self, nums, start, end):

        num_i, num_i_1 = nums[start], 0

        for i in xrange(start + 1, end):

            num_i_1, num_i_2 = num_i, num_i_1

            num_i = max(nums[i] + num_i_2, num_i_1);

        return num_i

C++:　　

class Solution {

public:

    int rob(vector<int>& nums) {

        if (nums.size() == 0) {

            return 0;

        }

        if (nums.size() == 1) {

            return nums[0];

        }

        return max(robRange(nums, 0, nums.size() - 1), // Include the first one of nums without the last one.

                   robRange(nums, 1, nums.size()));    // Include the last one of nums without the first one.

    }

    int robRange(vector<int>& nums, int start, int end) {

        int num_i = nums[start], num_i_1 = 0, num_i_2 = 0;

        for (int i = start + 1; i < end; ++i) {

            num_i_2 = num_i_1;

            num_i_1 = num_i;

            num_i = max(nums[i] + num_i_2, num_i_1);

        }

        return num_i;

    }

};

C++:

class Solution {

public:

    int rob(vector<int>& nums) {

        if (nums.size() <= 1) return nums.empty() ? 0 : nums[0];

        return max(rob(nums, 0, nums.size() - 1), rob(nums, 1, nums.size()));

    }

    int rob(vector<int> &nums, int left, int right) {

        int a = 0, b = 0;

        for (int i = left; i < right; ++i) {

            int m = a, n = b;

            a = n + nums[i];

            b = max(m, n);

        }

        return max(a, b);

    }

};

类似题目：

[LeetCode] 198. House Robber 打家劫舍

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 213. House Robber II 打家劫舍 II

All LeetCode Questions List 题目汇总

最新文章

热门文章