打家劫舍

怎样从“houses=[2,7,9,3,1],不能偷相邻,最大 2+9+1=12。”推导出 线性 DP · 打家劫舍，并证明每次状态变化都不会漏掉答案？

中心结论：dp[i]=max(dp[i-1], nums[i]+dp[i-2]);滚动变量。

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

在本站主例中，houses=[2,7,9,3,1],不能偷相邻,最大 2+9+1=12。

算法最终需要得到或观察：最大 12。

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 prev1/prev2、i。
3. 3转移每一步按照 dp[i]=max(dp[i-1], nums[i]+dp[i-2]);滚动变量。
4. 4收尾读取 最大 12。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：prev1/prev2、i。

你是一个专业的小偷，打算洗劫一条街的所有房子。每个房子里面有不同价值的宝物，但是如果你选择偷窃连续的 2 栋房子，就会触发警报系统，编程求出你最多可以偷窃价值多少的宝物？ 这一题可以用 DP 来解答，也可以用找规律的方法来解答。 DP 的状态定义是：`dp[i]` 代表抢 `nums[0,i]` 这个区间内房子的最大值，状态转移方程是 `dp[i] = max(dp[i-1], nums[i]+dp[i-2])` 。可以优化迭代的过程，用两个临时变量来存储中间结果，以节约辅助空间。

dp[i]=max(dp[i-1], nums[i]+dp[i-2]);滚动变量。

执行过程中持续维护：prev1/prev2、i。

正确性依赖以下不变量：到 i 的最优:不偷 i 或 偷 i+前 i-2 最优。

面试时可以压缩为：滚动 DP O(n)/O(1)。

落到当前题，执行机制可以压缩为：dp[i]=max(dp[i-1], nums[i]+dp[i-2]);滚动变量。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入houses=[2,7,9,3,1],不能偷相邻,最大 2+9+1=12。 因为：dp[i]=max(dp[i-1], nums[i]+dp[i-2]);滚动变量。
2. 2dp[i] = 前 i 间能偷的最大金额准备扫描每间房。 因为：偷 i 则不能偷 i-1。
3. 3第 1 间:偷 7 vs 不偷 2 → 7滚动更新 prev2/prev1。 因为：线性 DP O(n)。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5第 3 间:偷 10 vs 不偷 11 → 11滚动更新 prev2/prev1。 因为：线性 DP O(n)。
6. 6第 4 间:偷 12 vs 不偷 11 → 12滚动更新 prev2/prev1。 因为：线性 DP O(n)。
7. 7dp[i] = 前 i 间能偷的最大金额准备扫描每间房。 因为：偷 i 则不能偷 i-1。
8. 8收尾与复杂度最大 12。 因为：时间 O(n) · 空间 O(1)。dp[i]=max(dp[i-1], nums[i]+dp[i-2]);滚动变量。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 DP
func rob(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}
	// dp[i] 代表抢 nums[0...i] 房子的最大价值
	dp := make([]int, n)
	dp[0], dp[1] = nums[0], max(nums[1], nums[0])
	for i := 2; i < n; i++ {
		dp[i] = max(dp[i-1], nums[i]+dp[i-2])
	}
	return dp[n-1]
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// 解法二 DP 优化辅助空间，把迭代的值保存在 2 个变量中
func rob198_1(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	curMax, preMax := 0, 0
	for i := 0; i < n; i++ {
		tmp := curMax
		curMax = max(curMax, nums[i]+preMax)
		preMax = tmp
	}
	return curMax
}

// 解法三 模拟
func rob(nums []int) int {
	// a 对于偶数位上的最大值的记录
	// b 对于奇数位上的最大值的记录
	a, b := 0, 0
	for i := 0; i < len(nums); i++ {
		if i%2 == 0 {
			a = max(a+nums[i], b)
		} else {
			b = max(a, b+nums[i])
		}
	}
	return max(a, b)
}

func main() {
    // 1. 主例
    //    输入：mode="house-robber", nums=[2,7,9,3,1]
    //    期望：最大 12。
    //
    // 2. 失败 / 未命中
    //    检查：相邻约束导致不能简单贪心。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC213 环形；LC337 树
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意houses=[2,7,9,3,1],不能偷相邻,最大 2+9+1=12。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化dp[i]=max(dp[i-1], nums[i]+dp[i-2]);滚动变量。
4. 4证明到 i 的最优:不偷 i 或 偷 i+前 i-2 最优。
5. 5复杂度时间 O(n)，空间 O(1)