拓冰网站定制 
题目分析LeetCode 198. 打家劫舍你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金唯一的限制是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组 nums计算在不触动警报装置的情况下一夜之内能够偷窃到的最高金额。示例输入nums [1,2,3,1]输出4偷第 0 和第 2 间房1 3 4输入nums [2,7,9,3,1]输出12偷第 0、2、4 间房2 9 1 12核心思路这是一道经典的线性动态规划问题属于不能选相邻元素的最大化收益模型。对于每一间房屋只有两种选择偷当前收益 前前间房的最大收益 当前房屋金额不偷当前收益 前一间房的最大收益继承之前的最优结果取两者中的较大值即可。Java 实现方法一标准 DP 数组O(n) 空间class Solution {public int rob(int[] nums) {if (nums null || nums.length 0) {return 0;}if (nums.length 1) {return nums[0];}int n nums.length; int[] dp new int[n]; dp[0] nums[0]; dp[1] Math.max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i]); } return dp[n - 1]; }}状态定义 dp[i] 表示考虑前 i1 间房屋下标 0 到 i时能偷到的最高金额。状态转移方程 dp[i] max(dp[i-1], dp[i-2] nums[i])dp[i-1]不偷第 i 间房继承前一状态的最大值dp[i-2] nums[i]偷第 i 间房则不能偷第 i-1 间需加上第 i-2 间状态的最大值方法二空间优化O(1) 空间面试标准答案由于 dp[i] 只依赖 dp[i-1] 和 dp[i-2]可以用两个变量滚动更新将空间复杂度降至 O(1)。class Solution {public int rob(int[] nums) {int prev2 0; // 代表 dp[i-2]即前前间房的最大收益int prev1 0; // 代表 dp[i-1]即前一间房的最大收益for (int num : nums) { int cur Math.max(prev1, prev2 num); prev2 prev1; prev1 cur; } return prev1; }}执行过程以 nums [2,7,9,3,1] 为例轮次 当前房屋金额 prev2 prev1 cur当前最大收益初始 — 0 0 —第1轮 2 0 0 max(0, 02) 2第2轮 7 0 2 max(2, 07) 7第3轮 9 2 7 max(7, 29) 11第4轮 3 7 11 max(11, 73) 11第5轮 1 11 11 max(11, 111) 12最终返回 prev1 12 ✅方法三记忆化搜索自顶向下class Solution {private int[] memo;public int rob(int[] nums) { memo new int[nums.length]; Arrays.fill(memo, -1); return dfs(0, nums); } private int dfs(int i, int[] nums) { if (i nums.length) { return 0; } if (memo[i] ! -1) { return memo[i]; } // 偷当前房屋 vs 不偷当前房屋 memo[i] Math.max(nums[i] dfs(i 2, nums), dfs(i 1, nums)); return memo[i]; }}复杂度分析维度 方法一DP 数组 方法二空间优化 方法三记忆化搜索时间复杂度 O(n) O(n) O(n)空间复杂度 O(n) O(1) O(n) 递归栈 memo 数组面试延伸如果面试官追问可以补充说明为什么不能贪心只偷金额最大的 因为相邻限制导致局部最优不等于全局最优比如 [2,1,1,2]贪心选 224但 DP 也能得到 4但 [1,2,3,1] 贪心可能选错。如果房屋围成一圈怎么办 这就是 LeetCode 213. 打家劫舍 II拆成两种情况分别 DP不偷第一间房 vs 不偷最后一间房取较大值。如果房屋是二叉树结构怎么办 这就是 LeetCode 337. 打家劫舍 III用树形 DP每个节点返回偷和不偷两种状态的最大收益。这道题的 DP 模型还能用在哪些场景 “不能选相邻元素的最大化收益模型非常通用比如删除并获得点数”LeetCode 740、栅栏涂色等都属于同一类变形。这道题是动态规划的入门必刷题和爬楼梯、斐波那契数列属于同一类递推模型需要我顺带把打家劫舍系列的另外两道变形题环形房屋、二叉树房屋的思路也整理一下吗 千问 LeetCode 198. 打家劫舍 Java实现
题目分析LeetCode 198. 打家劫舍你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金唯一的限制是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组 nums计算在不触动警报装置的情况下一夜之内能够偷窃到的最高金额。示例输入nums [1,2,3,1]输出4偷第 0 和第 2 间房1 3 4输入nums [2,7,9,3,1]输出12偷第 0、2、4 间房2 9 1 12核心思路这是一道经典的线性动态规划问题属于不能选相邻元素的最大化收益模型。对于每一间房屋只有两种选择偷当前收益 前前间房的最大收益 当前房屋金额不偷当前收益 前一间房的最大收益继承之前的最优结果取两者中的较大值即可。Java 实现方法一标准 DP 数组O(n) 空间class Solution {public int rob(int[] nums) {if (nums null || nums.length 0) {return 0;}if (nums.length 1) {return nums[0];}int n nums.length; int[] dp new int[n]; dp[0] nums[0]; dp[1] Math.max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i]); } return dp[n - 1]; }}状态定义 dp[i] 表示考虑前 i1 间房屋下标 0 到 i时能偷到的最高金额。状态转移方程 dp[i] max(dp[i-1], dp[i-2] nums[i])dp[i-1]不偷第 i 间房继承前一状态的最大值dp[i-2] nums[i]偷第 i 间房则不能偷第 i-1 间需加上第 i-2 间状态的最大值方法二空间优化O(1) 空间面试标准答案由于 dp[i] 只依赖 dp[i-1] 和 dp[i-2]可以用两个变量滚动更新将空间复杂度降至 O(1)。class Solution {public int rob(int[] nums) {int prev2 0; // 代表 dp[i-2]即前前间房的最大收益int prev1 0; // 代表 dp[i-1]即前一间房的最大收益for (int num : nums) { int cur Math.max(prev1, prev2 num); prev2 prev1; prev1 cur; } return prev1; }}执行过程以 nums [2,7,9,3,1] 为例轮次 当前房屋金额 prev2 prev1 cur当前最大收益初始 — 0 0 —第1轮 2 0 0 max(0, 02) 2第2轮 7 0 2 max(2, 07) 7第3轮 9 2 7 max(7, 29) 11第4轮 3 7 11 max(11, 73) 11第5轮 1 11 11 max(11, 111) 12最终返回 prev1 12 ✅方法三记忆化搜索自顶向下class Solution {private int[] memo;public int rob(int[] nums) { memo new int[nums.length]; Arrays.fill(memo, -1); return dfs(0, nums); } private int dfs(int i, int[] nums) { if (i nums.length) { return 0; } if (memo[i] ! -1) { return memo[i]; } // 偷当前房屋 vs 不偷当前房屋 memo[i] Math.max(nums[i] dfs(i 2, nums), dfs(i 1, nums)); return memo[i]; }}复杂度分析维度 方法一DP 数组 方法二空间优化 方法三记忆化搜索时间复杂度 O(n) O(n) O(n)空间复杂度 O(n) O(1) O(n) 递归栈 memo 数组面试延伸如果面试官追问可以补充说明为什么不能贪心只偷金额最大的 因为相邻限制导致局部最优不等于全局最优比如 [2,1,1,2]贪心选 224但 DP 也能得到 4但 [1,2,3,1] 贪心可能选错。如果房屋围成一圈怎么办 这就是 LeetCode 213. 打家劫舍 II拆成两种情况分别 DP不偷第一间房 vs 不偷最后一间房取较大值。如果房屋是二叉树结构怎么办 这就是 LeetCode 337. 打家劫舍 III用树形 DP每个节点返回偷和不偷两种状态的最大收益。这道题的 DP 模型还能用在哪些场景 “不能选相邻元素的最大化收益模型非常通用比如删除并获得点数”LeetCode 740、栅栏涂色等都属于同一类变形。这道题是动态规划的入门必刷题和爬楼梯、斐波那契数列属于同一类递推模型需要我顺带把打家劫舍系列的另外两道变形题环形房屋、二叉树房屋的思路也整理一下吗