Java怎么解决打家劫舍的问题

# Java怎么解决打家劫舍的问题

## 问题描述

"打家劫舍"（House Robber）是一个经典的动态规划问题，题目描述如下：

> 假设你是一个专业的小偷，计划偷窃一条街上的房屋。每个房屋都藏有一定数量的金钱。相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚被闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你**在不触发警报的情况下**能够偷窃到的最高金额。

例如：
- 输入 `[1,2,3,1]`，输出 `4`（偷窃第1和第3个房屋）
- 输入 `[2,7,9,3,1]`，输出 `12`（偷窃第1、3、5个房屋）

---

## 动态规划解法

### 1. 定义状态
用 `dp[i]` 表示偷窃到第 `i` 个房屋时能获得的最大金额。

### 2. 状态转移方程
对于第 `i` 个房屋，小偷有两种选择：
- **偷窃当前房屋**：则不能偷窃前一个房屋，总金额为 `dp[i-2] + nums[i]`
- **不偷当前房屋**：总金额保持为 `dp[i-1]`

因此状态转移方程为：  
`dp[i] = max(dp[i-1], dp[i-2] + nums[i])`

### 3. 初始条件
- `dp[0] = nums[0]`（只有一间房屋时必偷）
- `dp[1] = max(nums[0], nums[1])`（两间房屋时选金额大的）

---

## Java代码实现

### 基础版本（空间复杂度O(n)）
```java
public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    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++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
    }
    return dp[nums.length - 1];
}

优化版本（空间复杂度O(1)）

public int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;
    for (int num : nums) {
        int curr = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

变种问题

1. 环形房屋（LeetCode 213）

当房屋排成环形时，首尾房屋视为相邻。解决方案： - 分别计算不偷第一间和不偷最后一间的最大值，取较大者。

public int robCircle(int[] nums) {
    if (nums.length == 1) return nums[0];
    return Math.max(
        rob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
        rob(Arrays.copyOfRange(nums, 1, nums.length))
    );
}

2. 二叉树房屋（LeetCode 337）

当房屋排列成二叉树结构时，需要后序遍历计算每个节点的偷/不偷状态。

public int rob(TreeNode root) {
    int[] res = dfs(root);
    return Math.max(res[0], res[1]);
}

private int[] dfs(TreeNode node) {
    if (node == null) return new int[2];
    int[] left = dfs(node.left);
    int[] right = dfs(node.right);
    int rob = node.val + left[1] + right[1];
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return new int[]{rob, notRob};
}

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：优化版本为O(1)，基础版本为O(n)

总结

通过动态规划可以高效解决打家劫舍及其变种问题。关键点在于： 1. 定义清晰的状态（如dp[i]） 2. 找到正确的状态转移方程 3. 处理边界条件 4. 根据问题变种调整策略（如环形、树形结构）

实际面试中，建议先写出基础DP解法，再逐步优化空间复杂度。 “`