LeetCode LCR 089. 打家劫舍

Categories:

题目描述
思路分析
1. 解法一：动态规划 + 空间优化（推荐）
2. 解法二：动态规划（数组版）
相似题目

题目描述

✅ LCR 089. 打家劫舍

思路分析

解法一：动态规划 + 空间优化（推荐）

核心思路：

核心约束：不能偷相邻房间，对每间房只有「偷」或「不偷」两个决策。

状态定义：dp[i] 表示偷到第 i 间房时能获得的最大金额。

状态转移：

不偷第 i 间：dp[i] = dp[i-1]

偷第 i 间：dp[i] = dp[i-2] + nums[i]

取最大：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

初始值：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])

空间优化：转移只依赖 dp[i-1] 和 dp[i-2]，用两个滚动变量代替数组，将空间从 O(n) 优化到 O(1)。

复杂度分析：

时间复杂度：O(n)，其中 n 为房屋数量

空间复杂度：O(1)，滚动变量优化

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // prev2 对应 dp[i-2]，prev1 对应 dp[i-1]
        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            // 偷第 i 间或不偷第 i 间，取最大值
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

func rob(nums []int) int {
    if len(nums) == 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 < len(nums); i++ {
        // 偷第 i 间或不偷第 i 间，取最大值
        curr := max(prev1, prev2+nums[i])
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}

解法二：动态规划（数组版）

核心思路：

与解法一思路相同，但显式维护 dp 数组，便于理解状态转移的全过程。

状态定义：dp[i] 表示考虑前 i 间房屋能偷到的最大金额。

状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

复杂度分析：

时间复杂度：O(n)，其中 n 为房屋数量

空间复杂度：O(n)，需要额外的 dp 数组

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        // 前两间取较大值
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            // 偷第 i 间或不偷第 i 间，取最大值
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    // 前两间取较大值
    dp[1] = max(nums[0], nums[1])
    for i := 2; i < len(nums); i++ {
        // 偷第 i 间或不偷第 i 间，取最大值
        dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    }
    return dp[len(nums)-1]
}

相似题目

题目	难度	考察点
213. 打家劫舍 II	中等	动态规划、环形处理
337. 打家劫舍 III	中等	动态规划、树形 DP
740. 删除并获得点数	中等	动态规划、打家劫舍变体
70. 爬楼梯	简单	线性 DP
2140. 解决智力问题	中等	动态规划、打家劫舍变体
1388. 3n 块披萨	困难	动态规划、环形打家劫舍
2320. 统计放置房子的方式数	中等	动态规划

本文作者: HGNULB

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