[!info] related notes 动态规划 线性 DP 打家劫舍

打家劫舍 II

题目链接：https://leetcode.cn/problems/house-robber-ii/

核心变化

房子围成一圈，所以第一个房子和最后一个房子不能同时偷。

关键拆分

环形不好直接做，但可以拆成两种情况：

• 偷的范围是 [0, n - 2]
• 偷的范围是 [1, n - 1]

分别做一次线性打家劫舍，取最大值即可。这两种情况分别排除末尾或开头，不要求一定偷另一个端点；n = 1 时不能按排除端点处理。

JavaScript

var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];

    function robLine(arr) {
        let prev2 = 0;
        let prev1 = 0;
        for (const x of arr) {
            const cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }

    return Math.max(robLine(nums.slice(0, n - 1)), robLine(nums.slice(1)));
};

时间 O(n)。此写法的 slice 会复制数组，额外空间为 O(n)；若给 robLine 传起止下标，才可把辅助空间降到 O(1)。