这个名字就有点怪怪的……
题目如下所示：
题目
这是一个很典型的动态规划问题，思路也比较简单。思路如下所示：
对于第二间房子之后的某一间房子（假设是第i间）来说，到了这间房子时的累计“偷窃”到的金额数可以这样表示：到第i间房子的累计量 = max(到第i-1间房子的累计量， 第i-2间房子的累计量+第i间房子的金额）。
max函数里面的两种情况分别对应从第i-2间房子直接跳到第i间房子和从第i-1间房子出发跳过第i间房子。这样的话，就不用去考虑特定的跳法，只要考虑某一部之前是怎么跳过来的就可以了。
关于步长的问题，为了使金额尽可能地大，所以步长只会是1或者2，更长的步长可以转化为更短的步长以获得更多的金额。
代码如下所示：
class Solution:
def rob(self, nums: List[int]) -> int:
#动态规划
if nums == []:
return 0
if len(nums) == 1:
return nums[0]
lens = len(nums)
sum_list = [0 for i in range(lens)]
sum_list[0], sum_list[1] = nums[0], max(nums[0], nums[1])
for i in range(2, lens):
sum_list[i] = max(nums[i]+sum_list[i-2], sum_list[i-1])
return max(sum_list)
写代码的时候日常疏忽了leetcode的奇怪情况，遇到了长度为0和1的list……图方便就直接对这两种情况进行判定了。
由于这道题的难度没有很大，因此我又看了一下这道题的升级版：打家劫舍Ⅱ。题目如下所示：
题目
这道题的难度升级就在于首尾相连成了一个环，首尾不能同时到达。
最开始的时候我想了一个方法，就是给每个房间进行标记，如果来到这个房间之前到过房间1（起始的那个），那么就标记为1，否则标记为0。这样在动态规划的过程中，就可以根据之前的房间的点的标记来确定后面的点的标记。
这个方法不难，但是刚写完我就发现不对劲，因为我发现了一个会使标记全为0的情况。如下所示：
会使标记全为0的情况
在这种情况下，从房间2开始之后的标记就全为0了，这样标记就失去了意义，这种方法显然不可行。
那要怎么样从原来的算法中改进到这个算法中呢？想了一会，我想到了一个很妙的方法，既然首尾不能同时到达，那就分两次调用之前的函数来计算，一次去头，一次去尾，把两次得到的结果取最大值，就得到想要的结果了。
事不宜迟，赶紧试一下，结果就行啦！代码如下所示：
class Solution:
def rob(self, nums: List[int]) -> int:
#因为要删掉一个元素，所以也要提前考虑好特殊情况
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
return max(self.rob1(nums[1:]), self.rob1(nums[:-1]))
def rob1(self, nums):
#这个就是上面那个初始版本的
if nums == []:
return 0
if len(nums) == 1:
return nums[0]
lens = len(nums)
sum_list = [0 for i in range(lens)]
sum_list[0], sum_list[1] = nums[0], max(nums[0], nums[1])
for i in range(2, lens):
sum_list[i] = max(nums[i]+sum_list[i-2], sum_list[i-1])
return max(sum_list)
然后我打算再看看打家劫舍Ⅲ的，然后发现是树结构的题目，我对树的操作还不熟悉，于是乎就不打算现在做了。题目如下所示：
题目
最后用一条十分搞笑的评论结束这篇文章：
程序员风评被害
