LeetCode Hot100（68/100）——198. 打家劫舍

题目链接

https://leetcode.cn/problems/house-robber/description/?envType=study-plan-v2&envId=top-100-liked

题目说明

你是一个专业小偷，计划偷窃沿街的房屋。每间房内有一定金额nums[i]。
相邻的房屋装有联动报警系统，如果同一晚偷了相邻两间房，就会触发报警。

请你返回在不触发报警的前提下，一晚能偷到的最高金额。

示例

• 输入：[1,2,3,1]
  输出：4
  解释：偷第 1 间（1）和第 3 间（3），总计 4。
• 输入：[2,7,9,3,1]
  输出：12
  解释：偷第 1 间（2）、第 3 间（9）、第 5 间（1），总计 12。

解题思路总览

解法一：纯递归（回溯思想）

原理

对于第i间房，有两种选择：

1. 不偷它：去看i-1的最优解
2. 偷它：那i-1不能偷，只能加上i-2的最优解

递归式：
f ( i ) = max ⁡ ( f ( i − 1 ) , f ( i − 2 ) + n u m s [ i ] ) f(i) = \max(f(i-1), f(i-2) + nums[i])f(i)=max(f(i−1),f(i−2)+nums[i])

Java 代码

classSolution{publicintrob(int[]nums){returndfs(nums,nums.length-1);}privateintdfs(int[]nums,inti){if(i<0)return0;if(i==0)returnnums[0];returnMath.max(dfs(nums,i-1),dfs(nums,i-2)+nums[i]);}}

复杂度分析

• 时间复杂度：O(2^n)（大量重复子问题）
• 空间复杂度：O(n)（递归栈）

该方法直观，但会超时，不推荐实际提交。

解法二：记忆化递归（自顶向下 DP）

原理

在纯递归的基础上，加一个memo[i]保存f(i)，避免重复计算。

Java 代码

importjava.util.Arrays;classSolution{privateint[]memo;publicintrob(int[]nums){memo=newint[nums.length];Arrays.fill(memo,-1);returndfs(nums,nums.length-1);}privateintdfs(int[]nums,inti){if(i<0)return0;if(memo[i]!=-1)returnmemo[i];intans=Math.max(dfs(nums,i-1),dfs(nums,i-2)+nums[i]);memo[i]=ans;returnans;}}

复杂度分析

• 时间复杂度：O(n)（每个状态只算一次）
• 空间复杂度：O(n)（memo + 递归栈）

解法三：动态规划数组（自底向上）

原理

定义dp[i]：考虑前i+1间房（0~i）时的最高金额。
转移：

• 不偷第i间：dp[i-1]
• 偷第i间：dp[i-2] + nums[i]
• 所以：
  dp[i] = max(dp[i-1], dp[i-2] + nums[i])

状态转移流程图

Java 代码

classSolution{publicintrob(int[]nums){intn=nums.length;if(n==1)returnnums[0];int[]dp=newint[n];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(inti=2;i<n;i++){dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);}returndp[n-1];}}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

解法四：空间优化 DP（推荐）

原理

观察到dp[i]只依赖dp[i-1]和dp[i-2]，无需整个数组。
用两个变量滚动维护：

• prev2 = dp[i-2]
• prev1 = dp[i-1]

每次更新：

• cur = max(prev1, prev2 + nums[i])
• 然后prev2 = prev1,prev1 = cur

时序图（变量更新）

Java 代码

classSolution{publicintrob(int[]nums){intprev2=0;// dp[i-2]intprev1=0;// dp[i-1]for(intx:nums){intcur=Math.max(prev1,prev2+x);prev2=prev1;prev1=cur;}returnprev1;}}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

示例推演（以[2,7,9,3,1]为例）

最终答案：12

各解法实现复杂度与性能对比