LeetCode 198：打家劫舍（House Robber）—— 题解 ✅

LeetCode 198：打家劫舍（House Robber）—— 题解 ✅

📖 内容概要

你是一个专业的小偷，计划偷窃沿街的房屋。
每间房都有一定数量的现金，但相邻的房屋装有连通的防盗系统，
如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。

求在不触动警报的前提下，一夜之内能够偷窃到的最高金额。

✅ 动态规划
✅ 线性 DP
✅ 面试高频题

💡 解题思路（核心）

一、状态定义

dp[i]=到第 i 间房子为止，能偷到的最大金额

二、状态转移方程（最重要）

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

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

三、边界条件

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

✅ AC 代码（Java）

classSolution{publicintrob(int[]nums){intlen=nums.length;if(len==1){returnnums[0];}int[]dp=newint[len];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(inti=2;i<len;i++){dp[i]=Math.max(dp[i-1],// 不偷当前房子dp[i-2]+nums[i]// 偷当前房子);}returndp[len-1];}}

⏱️ 复杂度分析

🚀 空间优化（进阶）

由于dp[i]只依赖前两个状态：

intprev2=nums[0];intprev1=Math.max(nums[0],nums[1]);for(inti=2;i<nums.length;i++){intcurr=Math.max(prev1,prev2+nums[i]);prev2=prev1;prev1=curr;}returnprev1;

✅ 一句话总结

要么不偷当前房子，要么偷当前房子 + 前两间的最优解，取最大值。

📌 面试加分点（建议记住）

• ✅ 为什么不能偷相邻房间？
• ✅ 为什么是dp[i-2] + nums[i]而不是dp[i-1] + nums[i]？
• ✅ 如何优化空间复杂度？
• ✅ 与「打家劫舍 II（环形房屋）」的关系