LeetCode LCR 089. 打家劫舍
题目描述
题意分析
在非负整数数组中选择一些下标，要求任意两个被选下标都不相邻，使选中金额之和最大。没有必须选择多少间房的限制，也不要求选择最后一间。
单看某间房的金额无法决定是否选它，因为放弃它可能换来两侧更大的总收益。可以按当前房屋“选或不选”分类，把问题转化为较短前缀的最优值。
解法：前缀最优的选与不选
核心思路
[!blue]
f[i]表示只考虑前i间房，即nums[0..i-1]时的最大合法金额。它包含最后一间选与不选的两种可能，不表示一定选择了nums[i-1]。处理第
i间房时分两种情况：不选它，剩下的最优值就是f[i-1]；选它，就必须排除第i-1间房，前面可以接上前i-2间的任意合法方案，最优值为f[i-2] + nums[i-1]。因此：
f[i] = max(f[i-1], f[i-2] + nums[i-1])。任何合法方案都属于其中一个分支，而两个分支构造出的方案也都不会出现相邻冲突。对已经确定的分支，用对应前缀的最优方案替换较差方案不会影响当前选择，所以只保留最优金额就足够，不必记录具体偷了哪些房屋。
f[0] = 0表示没有房屋，f[1] = nums[0]利用了金额非负这一条件。从i = 2向后计算时，前两个依赖值已经求出；最终f[n]就覆盖整排房屋的全部选择。只有一间房时循环不执行，直接得到它的金额；全零输入也自然返回零。
解题步骤
- 创建长度为
n+1的数组，令f[0] = 0、f[1] = nums[0]。- 从前两间开始递推，比较不选当前房屋与选当前、排除相邻房屋的收益。
- 计算到前
n间后，返回f[n]。
代码实现
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// f[i]：只考虑前 i 家能偷到的最大金额；第 i 家对应 nums[i - 1]。
int[] f = new int[n + 1];
// f[0] = 0 由默认零值给出；只有一家时必偷。
f[1] = nums[0];
for (int i = 2; i <= n; ++i) {
// 左：不偷第 i 家；右：偷第 i 家，必须跳过第 i - 1 家。
f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
}
return f[n];
}
}
func rob(nums []int) int {
n := len(nums)
// f[i]：只考虑前 i 家能偷到的最大金额；第 i 家对应 nums[i-1]。
f := make([]int, n+1)
// f[0] = 0 由默认零值给出；只有一家时必偷。
f[1] = nums[0]
for i := 2; i <= n; i++ {
// 左：不偷第 i 家；右：偷第 i 家，必须跳过第 i-1 家。
f[i] = max(f[i-1], f[i-2]+nums[i-1])
}
return f[n]
}
复杂度分析
- 时间复杂度：$O(n)$，每个前缀只计算两个候选值。
- 空间复杂度：$O(n)$，保存
n+1个前缀状态；只需返回金额时，也可以用两个变量保存相邻状态。
关键点总结
[!green]
- 状态按房屋数量编号，前
i间中的最后一间是nums[i-1]。- 选当前房屋时接
f[i-2]，通过排除邻居保证任意前缀最优方案都能与当前选择共存。f[i]已经比较选与不选，不需要强制最后一间被选，也不需要再遍历所有前缀取最大值。
易错点总结
[!yellow]
- 选当前房屋时若加上
f[i-1]，这个前缀可能已经选择了相邻房屋，会得到非法金额。- 不能混淆前缀数量下标与数组下标，转移中当前金额是
nums[i-1]。- 按单间金额贪心，可能错过两侧不相邻房屋的更大总收益。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 213. 打家劫舍 II | 中等 | 增加首尾相邻条件后，不能同时选择两端，需要拆成两条线性区间。 |
| 337. 打家劫舍 III | 中等 | 把线性相邻限制扩展到父子节点不能同时选择，状态仍是选与不选。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！