House Robber
房子沿着街道排成一排，nums[i] 表示第 i 间房子里的钱。你可以选择从任意房子里拿钱，但不能从两间相邻的房子里同时拿钱。返回你能拿到的最大总金额。
函数
- numsinteger-array
- 按街道顺序排列的每栋房屋中的金额
- 返回值integer
- 在不同时从相邻两栋房子取钱的情况下，你能拿到的最大总额
约束条件
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- 答案最大为
5 × 106，因此可以用有符号 32 位整数表示。
示例
- 输入
- nums = [5, 3, 4, 11, 2]
- 输出
- 16
- 解释
- 从第 0 栋和第 3 栋房子中取出 5 和 11，得到 16。可以连续跳过两栋房子，而且这种方案胜过其他所有方案：5 + 4 + 2 = 11，而 3 + 11 = 14。
- 输入
- nums = [3, 10, 3]
- 输出
- 10
- 解释
- 两端的房子加起来是 3 + 3 = 6。中间的房子单独是 10，选它就不能选它两边的房子。
- 输入
- nums = [2, 9, 3, 1, 8]
- 输出
- 17
- 解释
- 9 和 8 分别位于第 1 栋和第 4 栋房子里，它们不是相邻的，所以总和是 17。从头开始隔一栋房子取一栋，得到的只有 2 + 3 + 8 = 13。
进阶
返回要取的房屋以及总数。要重建这个列表，你必须保留表格中的哪些内容？两个累计值还能做到吗？
提示
逐个打开提示，每个都会多透露一点。
看看最后一栋房子。一个方案要么选择它，要么跳过它。每种选择会留下什么问题需要你解决？
如果跳过第
k-1间房子，最佳结果就是前k-1间房子的最佳结果。如果选择这间房子，就把nums[k-1]加到前k-2间房子的最佳结果上。k间房子的答案就是两者中较大的那个。从街道起点开始填写这些最优总数，没有房子时从 0 开始。每个总数只需要前两个总数，所以两个变量就够了。
题解
走捷径行不通：隔一户取一次会漏掉 [5, 3, 4, 11, 2] 中的 5 和 11，而先取最富有的人家，在 [3, 4, 3] 这个例子中也会吃亏。你可以一次决定是否取一家：截至某一户的最优总额，只取决于截至它前两户的最优总额。
在每栋房子处都尝试两种选择
结果正确，但无法在最大的测试中运行完毕
思路
每种方案要么跳过最后一栋房子，要么选择它。跳过它时，最优方案就是前 n-1 栋房子的最优方案；选择它时，就把 nums[n-1] 加到前 n-2 栋房子的最优方案上。因此，most(k) = max(most(k-1), most(k-2) + nums[k-1])，其中 most(0) = 0，most(1) = nums[0]。这两个分支涵盖了所有方案，因此答案是正确的。
这两个分支会重复计算：most(k-1) 会再次计算 most(k-2)，调用次数会像斐波那契数列一样增长，大约为 1.6^n。40 栋房子需要调用 3 亿多次，而 n 最大可达 10^4。
算法
- 编写一个辅助函数
most(k)，返回你从前k栋房子中最多能拿到的金额。 - 当
k为 0 时返回 0，当k为 1 时返回nums[0]。 - 否则，计算
skip = most(k-1)和take = most(k-2) + nums[k-1]。 - 返回两者中较大的值。答案是
most(n)。
def rob(nums):
def most(k):
# The most you can take from the first k houses
if k == 0:
return 0
if k == 1:
return nums[0]
# Skip house k-1, or take it and skip house k-2
return max(most(k - 1), most(k - 2) + nums[k - 1])
return most(len(nums))自底向上的表
思路
递归只会询问从 most(0) 到 most(n)：共 n + 1 个问题。把每个问题的答案只计算一次，并存入表 best，从 best[0] = 0 和 best[1] = nums[0] 开始，再从 k = 2 向上填充，这样每次读取的两个条目都已经有值。
对于 [5, 3, 4, 11, 2]，表中的值是 0, 5, 5, 9, 16, 16。当 k = 4 时，跳过第 3 间房会保留 best[3] = 9，而在 best[2] = 5 的基础上选择 11 会得到 16，因此后者更大。每个条目只需进行一次比较：时间复杂度为 O(n)，空间复杂度为 O(n)。
算法
- 创建一个包含 n + 1 个条目的表
best。 - 设置
best[0] = 0和best[1] = nums[0]。 - 对于从 2 到 n 的
k，将best[k]设置为best[k-1]和best[k-2] + nums[k-1]中较大的值。 - 返回
best[n]。
def rob(nums):
n = len(nums)
# best[k] is the most you can take from the first k houses
best = [0] * (n + 1)
best[1] = nums[0]
for k in range(2, n + 1):
# Skip house k-1, or take it on top of the best from the first k-2 houses
best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
return best[n]两个累计总数
思路
每一项只读取它前面的两项，因此只需保留两个数字，而不用保留整张表：twoBack 和 oneBack，分别表示到前两栋房子为止和到前一栋房子为止能得到的最大总数。对于存有 x 的房子，新的最大值是 max(oneBack, twoBack + x)；然后将两个值依次向前移动。两者都从 0 开始，表示第一栋房子之前的空街道，因此只有一栋房子的街道不需要特殊处理。时间复杂度仍为 O(n)，内存复杂度降至 O(1)。
算法
- 将
twoBack和oneBack设为 0。 - 对于
nums中的每个数x，计算current = max(oneBack, twoBack + x)。 - 将
oneBack移到twoBack中，然后将current移到oneBack中。 - 处理完最后一栋房子后，返回
oneBack。
def rob(nums):
# The best totals from the houses up to two back and up to one back
two_back, one_back = 0, 0
for amount in nums:
# Skip this house, or take it on top of the best from two back
two_back, one_back = one_back, max(one_back, two_back + amount)
return one_back
易错点和边界情况
- 在把
oneBack复制到twoBack之前就覆盖了oneBack。这样下一间房屋就会读取错误的总金额。先计算新的最大值，再移动变量，或者一次性给两者赋值。 - 读取
nums[1]，或者预先设置best[1]和best[2]。这两种做法在只有一间房屋的街道上都会出错，例如[0]。 - 在 Lua 和 R 中，数组从 1 开始计数，所以房屋
k-1中的钱是nums[k]。
常见问题3
打家劫舍的时间复杂度和空间复杂度是多少？
动态规划只会遍历每栋房子一次，因此时间复杂度为 O(n)。完整的表会占用 O(n) 空间，只保留最近的两个总数就能将空间复杂度降至 O(1)。不保存答案的普通递归会产生约 1.6^n 次调用。
为什么隔一户偷一户不能解决“打家劫舍”问题？
最优方案有时会连续跳过两栋房子。在 [10, 1, 1, 10] 中，偶数位置的房子和奇数位置的房子总和都是 11，而第一栋和最后一栋房子的总和是 20。
当房子围成一个圆圈时，如何解决“打家劫舍”问题？
在圆环中，第一间房子和最后一间房子相邻，因此方案最多只能选其中一间。将直线街道的解法运行两次，一次不考虑最后一间房子，一次不考虑第一间房子，然后返回较大的结果。只有一间房子时是特殊情况，答案就是这间房子。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def rob(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [5, 3, 4, 11, 2]
预期输出
16