vvrf / DSA.log

问题拆解

一排房子各有金额，不能偷相邻的两间，问最多能偷多少。贪心地“专挑金额大的偷”或“隔一间偷一间”都不对：[2, 7, 9, 3, 1] 的最优解是偷 2、9、1，跳过的间隔并不均匀，局部最大也不保证全局最大。

还是按“最后一间”做决策。设 f(i) 为“只考虑前 i 间房能偷到的最大金额”，第 i 间只有两种可能：偷它，那第 i-1 间必须放弃，收益是 f(i-2) + nums[i]；不偷它，收益就是 f(i-1)。两者取大即为 f(i)。

f(i) = max(f(i-1), f(i-2) + nums[i])——把爬楼梯递推式里的“加法”换成“取最大”，计数问题就变成了最优化问题，骨架一模一样。

状态只依赖前两项，和爬楼梯一样用两个变量滚动，空间 O(1)。

滚动两个变量

public int rob(int[] nums) {
    int prev = 0, cur = 0; // 分别是 f(i-2) 和 f(i-1)
    for (int x : nums) {
        int next = Math.max(cur, prev + x); // 不偷这间 vs 偷这间
        prev = cur;
        cur = next;
    }
    return cur;
}

def rob(nums: List[int]) -> int:
    prev = cur = 0  # 分别是 f(i-2) 和 f(i-1)
    for x in nums:
        prev, cur = cur, max(cur, prev + x)  # 不偷这间 vs 偷这间
    return cur

func rob(nums []int) int {
    prev, cur := 0, 0 // 分别是 f(i-2) 和 f(i-1)
    for _, x := range nums {
        prev, cur = cur, max(cur, prev+x) // 不偷这间 vs 偷这间
    }
    return cur
}

pub fn rob(nums: Vec<i32>) -> i32 {
    let (mut prev, mut cur) = (0, 0); // 分别是 f(i-2) 和 f(i-1)
    for x in nums {
        let next = cur.max(prev + x); // 不偷这间 vs 偷这间
        prev = cur;
        cur = next;
    }
    cur
}

把初值设成 prev = cur = 0（对应“0 间房收益为 0”），循环就能从第一间房统一开始，不用为 nums 长度为 1 或 2 单独写分支——这是滚动变量写法里最省心的边界处理。另一个理解上的易错点：f(i) 的含义是“前 i 间的最优”，而不是“偷了第 i 间的最优”，所以“不偷”分支直接继承 f(i-1)，不存在“连续两间都不偷”被漏掉的问题——那种方案已经包含在更早的 f 值里了。

复杂度

指标	复杂度	原因
时间	`O(n)`	每间房做一次两分支决策
空间	`O(1)`	只滚动前两个状态

可以迁移的模式

“选或不选，选了就限制邻居”的线性决策，状态转移都是 max(跳过, 隔项 + 当前)；
初值取“0 个元素的平凡解”，常能消掉短数组的特判分支；
同一副递推骨架，把 + 换成 max 就从计数变成最优化——识别同构比记题解更值钱。

打家劫舍 II（环形）和 III（树形）都是往这个转移上加一层结构：前者拆成两段线性，后者把“偷/不偷”挂到树的后序遍历上。