LeetCode 198打家劫舍House Robber—— 题解 ✅ 内容概要你是一个专业的小偷计划偷窃沿街的房屋。每间房都有一定数量的现金但相邻的房屋装有连通的防盗系统如果两间相邻的房屋在同一晚上被闯入系统会自动报警。求在不触动警报的前提下一夜之内能够偷窃到的最高金额。✅ 动态规划✅ 线性 DP✅ 面试高频题 解题思路核心一、状态定义dp[i]到第 i 间房子为止能偷到的最大金额二、状态转移方程最重要对于第i间房子有两种选择选择说明金额不偷继承前一家的最大金额dp[i-1]偷加上前两家的金额dp[i-2] nums[i]dp[i]max(dp[i-1],dp[i-2]nums[i])三、边界条件情况说明只有一间房只能偷这一间有两间房偷金额较大的那一间dp[0]nums[0];dp[1]max(nums[0],nums[1]);✅ AC 代码JavaclassSolution{publicintrob(int[]nums){intlennums.length;if(len1){returnnums[0];}int[]dpnewint[len];dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);for(inti2;ilen;i){dp[i]Math.max(dp[i-1],// 不偷当前房子dp[i-2]nums[i]// 偷当前房子);}returndp[len-1];}}⏱️ 复杂度分析指标复杂度时间复杂度O(n)空间复杂度O(n)可优化为 O(1) 空间优化进阶由于dp[i]只依赖前两个状态intprev2nums[0];intprev1Math.max(nums[0],nums[1]);for(inti2;inums.length;i){intcurrMath.max(prev1,prev2nums[i]);prev2prev1;prev1curr;}returnprev1;✅ 一句话总结要么不偷当前房子要么偷当前房子 前两间的最优解取最大值。 面试加分点建议记住✅ 为什么不能偷相邻房间✅ 为什么是dp[i-2] nums[i]而不是dp[i-1] nums[i]✅ 如何优化空间复杂度✅ 与「打家劫舍 II环形房屋」的关系
LeetCode 198：打家劫舍（House Robber）—— 题解 ✅
发布时间：2026/6/6 18:19:59
LeetCode 198打家劫舍House Robber—— 题解 ✅ 内容概要你是一个专业的小偷计划偷窃沿街的房屋。每间房都有一定数量的现金但相邻的房屋装有连通的防盗系统如果两间相邻的房屋在同一晚上被闯入系统会自动报警。求在不触动警报的前提下一夜之内能够偷窃到的最高金额。✅ 动态规划✅ 线性 DP✅ 面试高频题 解题思路核心一、状态定义dp[i]到第 i 间房子为止能偷到的最大金额二、状态转移方程最重要对于第i间房子有两种选择选择说明金额不偷继承前一家的最大金额dp[i-1]偷加上前两家的金额dp[i-2] nums[i]dp[i]max(dp[i-1],dp[i-2]nums[i])三、边界条件情况说明只有一间房只能偷这一间有两间房偷金额较大的那一间dp[0]nums[0];dp[1]max(nums[0],nums[1]);✅ AC 代码JavaclassSolution{publicintrob(int[]nums){intlennums.length;if(len1){returnnums[0];}int[]dpnewint[len];dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);for(inti2;ilen;i){dp[i]Math.max(dp[i-1],// 不偷当前房子dp[i-2]nums[i]// 偷当前房子);}returndp[len-1];}}⏱️ 复杂度分析指标复杂度时间复杂度O(n)空间复杂度O(n)可优化为 O(1) 空间优化进阶由于dp[i]只依赖前两个状态intprev2nums[0];intprev1Math.max(nums[0],nums[1]);for(inti2;inums.length;i){intcurrMath.max(prev1,prev2nums[i]);prev2prev1;prev1curr;}returnprev1;✅ 一句话总结要么不偷当前房子要么偷当前房子 前两间的最优解取最大值。 面试加分点建议记住✅ 为什么不能偷相邻房间✅ 为什么是dp[i-2] nums[i]而不是dp[i-1] nums[i]✅ 如何优化空间复杂度✅ 与「打家劫舍 II环形房屋」的关系
