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

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

📖 内容概要

你是一个专业的小偷，计划偷窃沿街的房屋。
所有房屋围成一圈，这意味着第一间房和最后一间房相邻。
如果两间相邻的房屋在同一晚上被闯入，系统会自动报警。

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

✅ 动态规划
✅ 环状结构拆环
✅ 基于 LeetCode 198 的变形

💡 解题思路（核心）

一、关键难点：环形限制

由于房屋是环形：

• 偷了第 1 间 →不能偷第 n 间
• 偷了第 n 间 →不能偷第 1 间

二、拆环为链（核心思想）

将环形问题拆分为两个线性问题：

✅ 两种情况互不冲突
✅ 分别用「打家劫舍 I」求解
✅ 取最大值

三、状态转移（复用 198）

dp[i]=max(dp[i-1],// 不偷当前dp[i-2]+nums[i]// 偷当前)

✅ AC 代码（Java）

classSolution{publicintrob(int[]nums){intlen=nums.length;if(len==1){returnnums[0];}// 拆成两个线性问题int[]a=Arrays.copyOf(nums,len-1);// 不含最后一间int[]b=Arrays.copyOfRange(nums,1,len);// 不含第一间returnMath.max(help(a),help(b));}// 线性打家劫舍（198 题）publicinthelp(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];}}

⏱️ 复杂度分析

🔍 与「打家劫舍 I」的对比

✅ 一句话总结

环形 = 去掉第一家 or 去掉最后一家，取两者最大值。

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

• ✅ 为什么不能直接用线性 DP？
• ✅ 为什么拆成两段就一定正确？
• ✅ 如何进一步优化空间？
• ✅ 与树形 DP（337）的区别