目录

1. 题目描述

2. 解题分析

2.1 直线排列的情况

 2.2 环形排列的情况

3. 代码实现

---

1. 题目描述

        你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

        给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。
     
示例 3：
输入：nums = [0]
输出：0 

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

        假设房子编号为0，1，2，。。。，由于是环形排列，从任何一间房子开始编号均可。

2.1 直线排列的情况

        首先撇开首尾相连这个因素，考虑呈直线排列的情况。

        由于有不能偷相邻房屋的限制，从一头开始偷，针对每一个房屋有偷还是不偷的选择，所以这其实是背包问题的基本型：0/1背包问题。而背包问题的经典解法必须是动态规划了。

        考虑从左到右的房间k（0,1,...）开始行动，将针对从房间k到末尾的所有房屋所能偷的最高金额记为dp(k)，

1. 如果偷了房屋k的话，房子(k+1)就必须跳过，接下来必须从房子(k+2)开始，总共能够获得的金额为Value[k] + dp(k+2)，其中Value[k]表示房子k中存放的金额
2. 如果跳过房屋k的话，接下来就可以从房子(k+1)开始，总共能够获得的金额为dp(k+1)，其中Value[k]表示房子k中存放的金额

        显然作为专业小偷你必须在以上两种选择之间进行评估并选择其中较大的那个方案，据此可以得到以下递推关系时：

  

 2.2 环形排列的情况

        本题稍微加了一点难度，将直线排列的房屋改成了环形排列。这样的话，等价于追加了一个约束条件，即房屋0和房屋k也不能都偷，最多只能二选一，当然也可以二者都不选。

        只要区分为以下两种情况考虑即可：

1. 不偷房子0。这种情况下问题就等价于从房屋1到末尾按直线排列的问题
2. 偷房子0。这种情况下问题就等价于除了房子0的金额以外，从房屋1到倒数第2间房子按直线排列的问题

        将以上分析结果翻译成代码即可。

3. 代码实现

from typing import List

class Solution:
    def robSlow(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums)
        
        return max(nums[0]+self.rob(nums[2:-1]), self.rob(nums[1:-1]))

    def robOpenloop(self, nums: List[int]) -> int:                                
        # print('robOpenloop: ', nums)
        memo = dict()

        def dp(k):
            if k in memo:
                return memo[k]
            
            if k >= len(nums):
                return 0
            if k == len(nums) - 1:
                return nums[k]
            if k == len(nums) - 2:
                return max(nums[k:k+2])
            
            a1 = nums[k] + dp(k+2)
            a2 = dp(k+1)
            
            ret = max(a1,a2)
            memo[k] = ret
            return ret
                                
        return dp(0)

    def rob(self, nums: List[int]) -> int:           
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums)
        
        return max(nums[0]+self.robOpenloop(nums[2:-1]), self.robOpenloop(nums[1:]))

import time
import random

if __name__ == '__main__':        
    
    sln = Solution()    
    
    nums = [2,3,2]
    print(nums, ' -> ', sln.rob(nums))
    
    nums = [1,2,3,1]
    print(nums, ' -> ', sln.rob(nums))
    
    tStart = time.time()        
    nums = [random.randint(0, 1000) for _ in range(50)]
    print(nums, ' -> ', sln.robOpenloop(nums))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')

 

回到本系列目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889