[LeetCode]House Robber II

题目描述:

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(入室盗贼)的扩展。

抢完上一条街的房屋之后,小偷又给自己找了一个不太引人注意的新作案场所。这一次,所有的房屋围成一个环形。也就是说第一个房屋和最后一个房屋相邻。与此同时,这些房屋的安保系统与上一条街的相同。

给定一组非负整数代表每一件房屋的金钱数,求解在不惊动警察的情况下一晚上最多可以抢到的钱数。

解题思路:

讨论是否抢劫第一件房屋。如果是,则不可以抢最后一件房屋。否则,可以抢最后一间房屋。

以此为依据,将环形DP问题转化为两趟线性DP问题,可以复用House Robber的代码。

另外需要特判一下只有一件房屋的情形。

Python代码:

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        if len(nums) == 1:
            return nums[0]
        return max(self.robLinear(nums[1:]), self.robLinear(nums[:-1]))
        
    # @param num, a list of integer
    # @return an integer
    def robLinear(self, num):
        size = len(num)
        odd, even = 0, 0
        for i in range(size):
            if i % 2:
                odd = max(odd + num[i], even)
            else:
                even = max(even + num[i], odd)
        return max(odd, even)

另附一个非常简洁的答案(https://leetcode.com/discuss/36586/6-lines-function-body):

class Solution:
    def rob(self, nums):
        def rob(nums):
            now = prev = 0
            for n in nums:
                now, prev = max(now, prev + n), now
            return now
        return max(rob(nums[len(nums) != 1:]), rob(nums[:-1]))

 

本文链接:http://bookshadow.com/weblog/2015/05/20/leetcode-house-robber-ii/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. liwzhi liwzhi 发布于 2015年10月12日 12:58 #

    class Solution(object):
    def rob(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums)==0:
    return 0

    if len(nums)<=3:
    return max(nums)

    dp = [0 for i in range(len(nums))]
    dp[0] = nums[0]
    dp[1] = nums[1]
    dp[2] = max(nums[1],nums[2])
    for i in range(3,len(nums)):
    dp[i] = max(dp[i-1],nums[i] + max(dp[1:i-1]))
    maxValue1 = dp[len(nums)-1]

    dp = [0 for i in range(len(nums))]
    dp[0] = nums[0]
    dp[1] = nums[1]
    for i in range(2,len(nums)-1):
    dp[i] = max(dp[i-1],nums[i] + max(dp[:i-1]))
    maxValue2 = dp[len(nums)-2]
    return max(maxValue1,maxValue2)

张贴您的评论