打家劫舍：选择或跳过的递推
将偷取或跳过的决策建模为 DP 递推式，把空间缩减为两个变量，并将解法扩展到环形房屋。
打家劫舍：选择或跳过的递推 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
打家劫舍问题
打家劫舍问题要求：给定一个由非负整数构成的数组，表示每栋房屋中的钱数，请找出在不偷窃相邻房屋的情况下能够偷得的最大金额。例如，[2, 7, 9, 3, 1] 的结果是 12（偷窃第 0、2、4 栋房屋）。这是一个经典的 1D DP 问题，您需要在每一步做出二选一的决定。
nums = [2, 7, 9, 3, 1]
# Can't rob adjacent houses
# Options: rob index 0 and 2 and 4 → 2+9+1=12
# or rob index 1 and 3 → 7+3=10
print('Max profit:', 12) # answer is 12定义递推关系
令 dp[i] 表示从前 i+1 栋房屋中偷得的最大金额。在每栋房屋 i 处，您有两个选择：跳过它（取 dp[i-1]），或偷窃它（取 nums[i] + dp[i-2]）。递推关系为 dp[i] = max(dp[i-1], nums[i] + dp[i-2])。这是基本的取或跳过模式，在许多 DP 问题中都会出现。
# Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# Base cases:
# dp[0] = nums[0] (only one house, rob it)
# dp[1] = max(nums[0], nums[1]) (take the richer of the two)
def rob(nums):
n = len(nums)
if n == 1: return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[-1]
print(rob([2, 7, 9, 3, 1])) # 12跟踪 DP 表
对于 [2, 7, 9, 3, 1]，我们逐步跟踪该表：dp[0] = 2，dp[1] = max(2, 7) = 7，dp[2] = max(7, 9+2) = 11，dp[3] = max(11, 3+7) = 11，dp[4] = max(11, 1+11) = 12。最终答案是 dp[4] = 12。手动跟踪该表可以确认递推关系在每个位置都正确处理了取和跳过两种选择。
nums = [2, 7, 9, 3, 1]
dp = [0] * len(nums)
dp[0] = 2
dp[1] = max(2, 7) # 7
for i in range(2, len(nums)):
skip = dp[i-1]
take = nums[i] + dp[i-2]
dp[i] = max(skip, take)
print(f'dp[{i}] = max({skip}, {nums[i]}+{dp[i-2]}) = {dp[i]}')
print('Answer:', dp[-1])将空间复杂度降至 O(1)
DP 表只会回看两个位置，因此可以用两个变量替代整个数组：prev2（前两个位置的值）和 prev1（前一个位置的值）。每次迭代后进行移位：prev2 = prev1，prev1 = current。这样可以在保持 O(n) 的 time 复杂度的同时，将内存占用从 O(n) 降至 O(1)。
def rob_optimised(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2 = prev1
prev1 = curr
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12
print(rob_optimised([1, 2, 3, 1])) # 4需要处理的边界情况
请务必针对边界情况测试您的解法：空数组（返回 0）、只有一个元素的数组（返回该元素），以及包含两个元素的数组（返回两者中的较大值）。在面试中主动提及并处理这些情况，可以体现您的全面性。if n == 1 守卫可以防止在访问 nums[1] 以计算 dp[1] 时发生索引越界。
def rob(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, nums[i] + prev2)
prev2, prev1 = prev1, curr
return prev1
print(rob([])) # 0
print(rob([5])) # 5
print(rob([3, 10])) # 10
print(rob([10, 3])) # 10打家劫舍 II：环形房屋
环形变体（LeetCode 213）将房屋排列成一个圆，第一个和最后一个房屋因此相邻。您不能直接应用线性递推关系。关键洞察是：要么偷窃第一栋房屋并排除最后一栋，要么排除第一栋房屋并包含最后一栋。分别在两个子数组上运行线性打家劫舍算法，然后取较大值。
def rob_linear(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
def rob_circular(nums):
if len(nums) == 1: return nums[0]
# Either include first (exclude last) or include last (exclude first)
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
print(rob_circular([2, 3, 2])) # 3
print(rob_circular([1, 2, 3, 1])) # 4贪心法为何在这里失败
一种朴素的贪心方法可能会尝试总是偷窃当前可选房屋中金额最大的一栋。然而，它会在 [2, 1, 1, 2] 这样的输入上失败：贪心法选择第 0 栋房屋（金额 2），然后选择第 3 栋房屋（金额 2），总金额为 4；但偷窃第 0 和第 2 栋房屋只能得到 3。等等——在这个例子中贪心法其实是有效的！但请尝试 [1, 3, 1, 3, 100]：贪心法选择金额为 3 的第 1 和第 3 栋房屋，得到 6，却错过了 1+1+100=102 的最优解。之所以必须使用 DP，是因为局部最优选择并不能保证全局最优。
# Greedy failure example
nums = [1, 3, 1, 3, 100]
# Greedy: pick max each step
# picks 3 (index 1), then 3 (index 3) → total 6
# DP optimal: pick 1 (index 0) + 1 (index 2) + 100 (index 4) → 102
def rob(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
return prev1
print(rob(nums)) # 102识别取或跳过模式
取或跳过模式并不局限于打家劫舍。每当您扫描一个数组，并在每个位置选择包含当前元素（跳过前一个元素）或排除当前元素（保留之前的结果）时，您面对的就是取或跳过 DP。请留意诸如不能有两个相邻元素或区间不能重叠之类的约束，它们通常提示您应用这种模式。
# General take-or-skip template
def take_or_skip(values, gap=1):
'''Max sum where selected elements must be at least gap+1 apart.'''
n = len(values)
if n == 0: return 0
# dp[i] = best up to index i
dp = [0] * (n + gap)
for i in range(n):
take = values[i] + (dp[i - 1] if i >= 1 else 0)
skip = dp[i + gap - 1] if i + gap - 1 < len(dp) else 0
dp[i + gap] = max(skip, take)
return dp[-1]
print(take_or_skip([2, 7, 9, 3, 1])) # house robber-like删除并获得点数变体
删除并获得点数（LeetCode 740）要求：对于每个选中的数字，您可以获得 num × count(num)，但必须删除 num-1 和 num+1 的所有出现次数。这个问题可以直接转化为打家劫舍：为所有值构造数组 earn[v] = v × count(v)，然后在该数组上运行打家劫舍算法。识别这种转化是重要的面试技能。
from collections import Counter
def delete_and_earn(nums):
if not nums: return 0
count = Counter(nums)
max_val = max(nums)
# earn[v] = total points from taking all v's
earn = [v * count[v] for v in range(max_val + 1)]
# Now run house robber on earn
prev2, prev1 = 0, 0
for e in earn:
prev2, prev1 = prev1, max(prev1, e + prev2)
return prev1
print(delete_and_earn([3, 4, 2])) # 6 (take 3+3=no, take 4+2=6)
print(delete_and_earn([2, 2, 3, 3, 3, 4])) # 9 (take all 3s)打家劫舍 III：二叉树
在打家劫舍 III中，房屋排列成一棵二叉树。您不能同时偷窃一个节点及其直接父节点。定义一个辅助函数，使其返回两个值：rob(node) → (rob_root, skip_root)。如果偷窃根节点，就将两个子节点的跳过值相加。如果跳过根节点，就将每个子节点的较优值相加。这是一个后序 DFS，并在每个节点处做出取或跳过的决定。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob_tree(root):
def dfs(node):
if not node: return (0, 0) # (rob, skip)
l_rob, l_skip = dfs(node.left)
r_rob, r_skip = dfs(node.right)
rob = node.val + l_skip + r_skip
skip = max(l_rob, l_skip) + max(r_rob, r_skip)
return (rob, skip)
return max(dfs(root))
# Tree: 3 -> 2,3 -> None,3,None,1
root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
print(rob_tree(root)) # 7复杂度与面试讨论
线性打家劫舍在采用双变量优化后，运行复杂度为 O(n) time，空间复杂度为 O(1)。环形变体同样为 O(n) time，因为它会调用线性版本两次。树形变体的复杂度为 O(n) time，空间复杂度为 O(h)，其中 h 是树的高度。在面试中，完成编码后请务必说明复杂度，并提及空间优化——这表明您考虑的不只是第一个可运行的解法。
# Summary of complexities
# Linear House Robber:
# Time: O(n), Space: O(1) with two-variable trick
# Circular House Robber:
# Time: O(n), Space: O(1) (two passes)
# Tree House Robber:
# Time: O(n), Space: O(h) call stack
# Quick benchmark
import time
import random
nums = [random.randint(0, 100) for _ in range(10**6)]
start = time.time()
prev2 = prev1 = 0
for n in nums:
prev2, prev1 = prev1, max(prev1, n + prev2)
print(f'1M elements in {time.time()-start:.3f}s, result={prev1}')快速检查
请检验您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学到了：取或跳过递推式 dp[i] = max(dp[i-1], nums[i] + dp[i-2])、使用两个滚动变量将 O(n) 空间降至 O(1)，以及将这一模式扩展到循环数组和二叉树。接下来，我们将使用卡丹算法探索最大子数组和最大乘积子数组问题。
常见问题解答
「打家劫舍：选择或跳过的递推」课时是免费的吗？
是的 — 「打家劫舍：选择或跳过的递推」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「打家劫舍：选择或跳过的递推」这节课中我会学到什么？
将偷取或跳过的决策建模为 DP 递推式，把空间缩减为两个变量，并将解法扩展到环形房屋。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「打家劫舍：选择或跳过的递推」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 打家劫舍：选择或跳过的递推
- 最大子数组和与最大乘积子数组
- 单词拆分与字符串分段
- 解码方法与路径计数