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

文章目录题目链接题目说明示例解题思路总览解法一纯递归回溯思想原理Java 代码复杂度分析解法二记忆化递归自顶向下 DP原理Java 代码复杂度分析解法三动态规划数组自底向上原理状态转移流程图Java 代码复杂度分析解法四空间优化 DP推荐原理时序图变量更新Java 代码复杂度分析示例推演以 [2,7,9,3,1] 为例各解法实现复杂度与性能对比题目链接https://leetcode.cn/problems/house-robber/description/?envTypestudy-plan-v2envIdtop-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。解题思路总览打家劫舍本质线性DP每间房只有偷/不偷两种决策状态定义dp[i] 前 i 间房的最高金额状态转移不偷第 i 间: dp[i-1]偷第 i 间: dp[i-2] nums[i]取最大值可选解法纯递归(指数级)记忆化递归DP数组(自底向上)空间优化DP(滚动变量)解法一纯递归回溯思想原理对于第i间房有两种选择不偷它去看i-1的最优解偷它那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(i0)return0;if(i0)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){memonewint[nums.length];Arrays.fill(memo,-1);returndfs(nums,nums.length-1);}privateintdfs(int[]nums,inti){if(i0)return0;if(memo[i]!-1)returnmemo[i];intansMath.max(dfs(nums,i-1),dfs(nums,i-2)nums[i]);memo[i]ans;returnans;}}复杂度分析时间复杂度O(n)每个状态只算一次空间复杂度O(n)memo 递归栈解法三动态规划数组自底向上原理定义dp[i]考虑前i1间房0~i时的最高金额。转移不偷第i间dp[i-1]偷第i间dp[i-2] nums[i]所以dp[i] max(dp[i-1], dp[i-2] nums[i])状态转移流程图不偷偷开始 i是否偷第 i 间?收益 dp[i-1]收益 dp[i-2] nums[i]dp[i] max(两者)处理 i1Java 代码classSolution{publicintrob(int[]nums){intnnums.length;if(n1)returnnums[0];int[]dpnewint[n];dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);for(inti2;in;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时序图变量更新curprev1prev2Loopcurprev1prev2Loopcur max(prev1, prev2 nums[i])prev2 - prev1prev1 - curJava 代码classSolution{publicintrob(int[]nums){intprev20;// dp[i-2]intprev10;// dp[i-1]for(intx:nums){intcurMath.max(prev1,prev2x);prev2prev1;prev1cur;}returnprev1;}}复杂度分析时间复杂度O(n)空间复杂度O(1)示例推演以[2,7,9,3,1]为例inums[i]选不偷dp[i-1]选偷dp[i-2]nums[i]dp[i]02--21727729711113311101141111212最终答案12各解法实现复杂度与性能对比解法核心思想时间复杂度空间复杂度实现复杂度性能表现适用场景纯递归暴力枚举偷/不偷O(2^n)O(n)低很差易超时仅用于理解问题记忆化递归递归 缓存子问题O(n)O(n)中优秀喜欢递归写法时DP数组自底向上填表O(n)O(n)中优秀且稳定面试常规写法空间优化DP滚动变量替代数组O(n)O(1)中偏低最优实战/提交推荐