打家劫舍——动态规划问题

题目描述你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入该系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例 示例 1输入[1, 2, 3, 1] 输出4 解释偷窃 1 号房屋 (金额 1)然后偷窃 3 号房屋 (金额 3)。偷窃到的最高金额 1 3 4。 示例 2 输入[2, 7, 9, 3, 1] 输出12 解释偷窃 1 号房屋 (金额 2)偷窃 3 号房屋 (金额 9)接着偷窃 5 号房屋 (金额 1)。偷窃到的最高金额 2 9 1 12。思路分析以及解法一、 核心思路选还是不选对于每一间房子小偷只有两个选择偷这一家那么为了安全前一家绝对不能偷。此时的最大收益 前前家的最大收益 当前家的金额。不偷这一家那么最大收益就等于前一家偷到现在的最大收益。小偷的目标是最大化总收益所以当前状态的最大收益就是上述两种选择中的较大值。二、 状态转移方程如果我们用 dp[i] 表示“偷到第 i 家时能获得的最高金额”那么状态转移方程非常直观dp[i]max(dp[i−1],dp[i−2]nums[i])dp[i - 1]代表不偷第 i 家直接继承前一家i-1的最高收益。dp[i - 2] nums[i]代表偷第 i 家那么必须跳过 i-1 家收益为前前家i-2的最高收益加上当前家的钱。三、 Java 代码实现基础 DP 版publicclassHouseRobber{publicintrob(int[]nums){intnnums.length;// 边界条件处理if(n0)return0;if(n1)returnnums[0];// 1. 定义 dp 数组int[]dpnewint[n];// 2. 初始化基础状态dp[0]nums[0];// 只有1家只能偷这家dp[1]Math.max(nums[0],nums[1]);// 有2家挑金额大的偷// 3. 状态转移从第3家索引2开始往后推for(inti2;in;i){dp[i]Math.max(dp[i-1],dp[i-2]nums[i]);}// 4. 返回最后一家算出的最大收益returndp[n-1];}}四、 进阶优化空间压缩O(1) 空间结合我们刚才聊过的“接雨水”双指针优化思想在打家劫舍中计算 dp[i] 时只依赖 dp[i-1] 和 dp[i-2]。因此我们根本不需要开辟一个长度为 n 的数组只需要两个变量滚动更新即可。publicclassHouseRobber{publicintrob(int[]nums){if(nums.length0)return0;// prev 代表 dp[i-2]curr 代表 dp[i-1]intprev0;intcurr0;for(intnum:nums){// 计算当前的 dp[i]inttempMath.max(curr,prevnum);// 滚动更新状态prevcurr;currtemp;}returncurr;}}五、 复杂度分析时间复杂度O(n)。只需遍历一次数组。空间复杂度基础版为 O(n)空间压缩版为 O(1)。