动态规划|相邻约束下的最优解(House Robber II )
动态规划|相邻约束下的最优解(House Robber II )
01
House Robber II
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 I 的题目：
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
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.
相邻房子不能同时偷，求在此约束下，偷n个房子获益的最大值。
02
分析
以上这个链接给出的是一个：最后一个房子不与第一个挨着，的解决方案，分析思路，代码都有。
那么，这个相对复杂点的问题与上面简单的这个区别是什么？
第一个(非圆形)：1->2->3
第二个(圆形)： 1->2->3->1
因此，圆形排布的房子，房子1具有特殊性，因为：
1) 房子1如果偷了，房子3也不能偷了，因此偷的序列切分为：1->2
2) 房子1如果没偷，偷的序列切分为：2->3
切分为这两种情况后，每种情况就可以套用第一个(非圆形)问题的解决思路了。
03
实现
动态规划|相邻约束下的最优解 House Robber I 代码：
def rob(self, nums): premax, maxval = 0,0 for val in nums: tmp = maxval maxval = val + premax premax = max(premax,tmp) return max(premax,maxval)
因为要复用这个代码，所以提出两个表示房子位置的变量。
class Solution: def rob(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums)==0: return 0 if len(nums)==1: return nums[0] return max( self.robp(nums,0,len(nums)-2), self.robp(nums,1,len(nums)-1) ) def robp(self,nums,lo,hi): premax, maxval = 0,0 for i, val in enumerate(nums): if i<lo or i>hi: continue tmp = maxval maxval = val + premax premax = max(premax,tmp) return max(premax,maxval)
以上，决策最优化简单应用。