目录
方法 1：朴素回溯（暴力递归）
思路
Java 实现
时空复杂度
问题
方法 2：记忆化搜索（自顶向下 DP）
思路
Java 实现
时空复杂度
优化点
方法 3：自底向上的动态规划（DP 数组）
思路
Java 实现
时空复杂度
优化点
方法 4：空间优化的动态规划（双变量）
思路
Java 实现
时空复杂度
优化点
优化变迁总结
打家劫舍问题的核心是 “相邻房屋不能同时偷”，我们从暴力回溯开始，逐步优化到空间最优的动态规划，下面分步骤解析：
方法 1：朴素回溯（暴力递归）
思路
通过递归枚举每个房屋的两种选择：偷当前房屋（则只能偷前 i-2 个房屋的最大金额 + 当前金额）、不偷当前房屋（则偷前 i-1 个房屋的最大金额）。状态定义：dfs(i)表示 “考虑前 i 个房屋时的最大偷窃金额”。
Java 实现
class Solution { public int rob(int[] nums) { return dfs(nums, nums.length - 1); } // 递归计算前i个房屋的最大金额 private int dfs(int[] nums, int i) { if (i < 0) return 0; // 边界：没有房屋时金额为0 // 选择1：不偷i，取前i-1的最大；选择2：偷i，取前i-2的最大+当前金额 return Math.max(dfs(nums, i - 1), dfs(nums, i - 2) + nums[i]); } }时空复杂度
- 时间复杂度：O(2n)（每个房屋分 2 种选择，递归树深度为 n，总节点数是2n级）
- 空间复杂度：O(n)（递归栈的深度为 n）
问题
存在大量重复计算：例如计算dfs(5)需要dfs(4)和dfs(3)，计算dfs(4)又需要dfs(3)和dfs(2)，dfs(3)会被多次计算，效率极低（n≥20 时就会超时）。
方法 2：记忆化搜索（自顶向下 DP）
思路
用 ** 备忘录（数组）** 存储已经计算过的dfs(i)结果，避免重复计算 —— 每次计算前先检查备忘录，若已存在结果则直接返回，否则计算后存入备忘录。
Java 实现
import java.util.Arrays; class Solution { private int[] memo; // 备忘录：存储每个i对应的最大金额 public int rob(int[] nums) { int n = nums.length; memo = new int[n]; Arrays.fill(memo, -1); // 初始化：-1表示该位置未计算（金额非负，不会和有效结果冲突） return dfs(nums, n - 1); } private int dfs(int[] nums, int i) { if (i < 0) return 0; if (memo[i] != -1) return memo[i]; // 已计算，直接返回 // 计算并存入备忘录 int res = Math.max(dfs(nums, i - 1), dfs(nums, i - 2) + nums[i]); memo[i] = res; return res; } }时空复杂度
- 时间复杂度：O(n)（每个 i 只计算 1 次）
- 空间复杂度：O(n)（备忘录数组 + 递归栈）
优化点
解决了 “重复计算” 的问题，将时间复杂度从指数级降到线性，但仍依赖递归栈。
方法 3：自底向上的动态规划（DP 数组）
思路
把 “自顶向下的递归” 改成 “自底向上的迭代”，用DP 数组存储每个位置的最大金额，彻底避免递归栈。状态定义：dp[i]表示 “前 i 个房屋的最大偷窃金额”。状态转移：
- 不偷第 i 个房屋：
dp[i] = dp[i-1]- 偷第 i 个房屋：
dp[i] = dp[i-2] + nums[i-1]（nums 索引比 dp 小 1，因为 dp [0] 对应 “0 个房屋”）
Java 实现
class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 0) return 0; // dp[i]：前i个房屋的最大金额（i从0到n） int[] dp = new int[n + 1]; dp[0] = 0; // 0个房屋，金额0 dp[1] = nums[0]; // 1个房屋，金额为nums[0] // 从第2个房屋开始迭代 for (int i = 2; i <= n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]); } return dp[n]; } }时空复杂度
- 时间复杂度：O(n)（仅需遍历 1 次）
- 空间复杂度：O(n)（DP 数组占用 n+1 空间）
优化点
用迭代替代递归，避免了递归栈溢出的风险，但空间仍依赖数组。
方法 4：空间优化的动态规划（双变量）
思路
观察状态转移：dp[i]只依赖dp[i-1]和dp[i-2]，因此不需要整个 DP 数组，只需用两个变量分别存储这两个依赖值即可。
Java 实现
class Solution { public int rob(int[] nums) { int f0 = 0; // 对应dp[i-2]（前i-2个房屋的最大金额） int f1 = 0; // 对应dp[i-1]（前i-1个房屋的最大金额） for (int x : nums) { int newF = Math.max(f1, f0 + x); // 计算当前房屋的最大金额 f0 = f1; // 更新f0为原来的f1（i-1 → i-2） f1 = newF; // 更新f1为当前的newF（i → i-1） } return f1; } }时空复杂度
- 时间复杂度：O(n)（遍历 1 次）
- 空间复杂度：O(1)（仅用 2 个变量）
优化点
将空间复杂度从O(n)降到O(1)，是该问题的最优空间方案。
优化变迁总结
朴素回溯（O(2^n)时间） ↓ 解决重复计算 记忆化搜索（O(n)时间，O(n)空间） ↓ 去掉递归栈，改为迭代 自底向上DP数组（O(n)时间，O(n)空间） ↓ 去掉冗余数组，用双变量替代 空间优化DP（O(n)时间，O(1)空间）
