213 House Robber
# 213 House Robber
题目来源：
https://leetcode.com/problems/house-robber-ii/description/
题意分析：
给定一个正整数列表，列表头尾相连成环，要求不能取相邻的正整数，输出能取出的数的和。
题目思路：
首先假设该列表不成环，那么就是经典的动态规划问题，设前i+1个正整数取到的最大和为sum[i],容易知道sum[0]=nums[0],sum[1]=max(nums[0],nums[1])。从i=2开始，sum[i]可以从两个方向获得，一是从sum[i-1]来，这时nums[i]不可取，二是从sum[i-2]来，这时nums[i]可取。两种方式都可能使sum[i]取得最大值，那么可以得到动态转移方程sum[i]=max(sum[i-1],(sum[i-2]+nums[i]))。
接下来取消假设，即该列表成环，那么跟不成环有什么不同呢？原来没成环时，首尾是可以一起选的，因为成环，首尾不能一起选了。那我们可以分两种情况，一是头可以选，尾不可以选，二是头不可以选，尾可以选。可以选并不是一定要选的意思。这样的话，一个环就可以分成两条不成环的列表了，一是nums[0:-1],一是nums[1:]。算出两个列表最后的sum取最大值就成。
测试之后发现漏了两种特殊情况：
第一种，举个栗子：[1,3,1,3,100]。显然答案是100+3=103但是根据思路,分成两列表[1,3,1,3]和[3,1,3,100],无法得到正确结果。原因是对于[3,1,3,100], 1 处默认的sum为1，但其实可以通过第一个3更新为3，但它又不能调用动态转移方程（因为不存在1的前两位），处理办法是
sum[3]=max(sum[2],(sum[1]+nums[3])，(sum[0]+nums[3]))。
这样就可以把后面的sum值都更新了。
第二种，列表长度为3的情况，分成了两个长度为2的列表，算法施展不开手脚。。
代码：
1. class Solution:
2. def rob(self, nums):
3. """
4. :type nums: List[int]
5. :rtype: int
6. """
7. if (nums==[]):
8. return 0
9. if (len(nums)==1):
10. return nums[0]
11. if (len(nums)==2):
12. return max(nums[0],nums[1])
13. if (len(nums)==3):
14. return max(nums[0],nums[1],nums[2])
15.
16. temp_res=[0]*(len(nums)-1)
17. temp_res[0]=nums[0]
18. temp_res[1]=nums[1]
19.
20. for i in range(2,len(nums)-1):
21. temp_res[i]=max(temp_res[i-1],temp_res[i-2]+nums[i])
22. if (i==3):
23. temp_res[i]=max(temp_res[i],temp_res[i-3]+nums[i])
24.
25. res=temp_res[len(nums)-2]
26.
27. nums=nums[1:]
28. temp_res=[0]*len(nums)
29. temp_res[0]=nums[0]
30. temp_res[1]=nums[1]
31. for i in range(2,len(nums)):
32. temp_res[i]=max(temp_res[i-1],temp_res[i-2]+nums[i])
33. if (i==3):
34. temp_res[i]=max(temp_res[i],temp_res[i-3]+nums[i])
35.
36. res=max(res,temp_res[len(nums)-1])
37.
38. return res
39.
40.
41.
提交细节：