LeetCode LCR 090. 打家劫舍 II

Categories:

题目描述
思路分析
1. 解法一：拆分环形为两次线性 DP（推荐）
2. 解法二：空间优化滚动变量
相似题目

题目描述

✅ LCR 090. 打家劫舍 II

思路分析

解法一：拆分环形为两次线性 DP（推荐）

核心思路：

本题与 198. 打家劫舍的区别在于房屋排列成环形，首尾相邻，不能同时偷窃首尾两间。

关键观察：对于环形数组，要么不包含首元素，要么不包含末元素，两者必居其一。因此可以将问题拆分为两个独立的线性打家劫舍问题：

情况一：不偷首元素，在 nums[1..n-1] 上做线性 DP

情况二：不偷末元素，在 nums[0..n-2] 上做线性 DP

两种情况取最大值即为答案。

线性 DP 状态转移：

定义 dp[i] 为偷到第 i 间房屋时能获得的最大收益：

dp[0] = nums[0]

dp[1] = max(nums[0], nums[1])

dp[i] = max(dp[i-1], dp[i-2] + nums[i])，i >= 2

复杂度分析：

时间复杂度：O(n)，其中 n 为数组 nums 的长度，两次线性扫描各 O(n)。

空间复杂度：O(n)，使用了大小为 n 的 dp 数组。

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }

        // 情况一：不偷首元素，在 nums[1..n-1] 上做线性 DP
        int case1 = robLinear(nums, 1, n - 1);
        // 情况二：不偷末元素，在 nums[0..n-2] 上做线性 DP
        int case2 = robLinear(nums, 0, n - 2);

        return Math.max(case1, case2);
    }

    private int robLinear(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }

        int[] dp = new int[end - start + 1];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);

        for (int i = 2; i <= end - start; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);
        }

        return dp[end - start];
    }
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    if n == 2 {
        return max(nums[0], nums[1])
    }

    // 情况一：不偷首元素，在 nums[1..n-1] 上做线性 DP
    case1 := robLinear(nums[1:])
    // 情况二：不偷末元素，在 nums[0..n-2] 上做线性 DP
    case2 := robLinear(nums[:n-1])

    return max(case1, case2)
}

func robLinear(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }

    // dp[i] 表示偷到第 i 间房屋时的最大收益
    dp := make([]int, n)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i := 2; i < n; i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    }

    return dp[n-1]
}

解法二：空间优化滚动变量

核心思路：

在线性 DP 中，dp[i] 只依赖 dp[i-1] 和 dp[i-2]，因此可以用两个变量滚动替代整个数组，将空间压缩至 O(1)。

同样拆分为不含首元素和不含末元素两次线性扫描，取最大值。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组 nums 的长度。

空间复杂度：O(1)，仅使用常数个滚动变量。

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }

        // 情况一：不偷首元素，在 nums[1..n-1] 上做滚动 DP
        int case1 = robLinear(nums, 1, n - 1);
        // 情况二：不偷末元素，在 nums[0..n-2] 上做滚动 DP
        int case2 = robLinear(nums, 0, n - 2);

        return Math.max(case1, case2);
    }

    private int robLinear(int[] nums, int start, int end) {
        // prev2 对应 dp[i-2]，prev1 对应 dp[i-1]
        int prev2 = nums[start];
        int prev1 = Math.max(nums[start], nums[start + 1]);

        for (int i = start + 2; i <= end; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
}

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    if n == 2 {
        return max(nums[0], nums[1])
    }

    // 情况一：不偷首元素，在 nums[1..n-1] 上做滚动 DP
    case1 := robLinearOpt(nums[1:])
    // 情况二：不偷末元素，在 nums[0..n-2] 上做滚动 DP
    case2 := robLinearOpt(nums[:n-1])

    return max(case1, case2)
}

func robLinearOpt(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }

    // prev2 对应 dp[i-2]，prev1 对应 dp[i-1]
    prev2 := nums[0]
    prev1 := max(nums[0], nums[1])

    for i := 2; i < n; i++ {
        curr := max(prev1, prev2+nums[i])
        prev2 = prev1
        prev1 = curr
    }

    return prev1
}

相似题目

题目	难度	考察点
198. 打家劫舍	中等	动态规划 / 线性 DP
337. 打家劫舍 III	中等	动态规划 / 树形 DP
740. 删除并获得点数	中等	动态规划 / 打家劫舍变形
2560. 打家劫舍 IV	中等	二分答案 + 贪心
376. 摆动序列	中等	动态规划 / 贪心
剑指 Offer 10- I. 斐波那契数列	简单	动态规划 / 滚动数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/73555304