企业官网建设流程全解析

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，该系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 示例 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){intn=nums.length;// 边界条件处理if(n==0)return0;if(n==1)returnnums[0];// 1. 定义 dp 数组int[]dp=newint[n];// 2. 初始化基础状态dp[0]=nums[0];// 只有1家，只能偷这家dp[1]=Math.max(nums[0],nums[1]);// 有2家，挑金额大的偷// 3. 状态转移：从第3家（索引2）开始往后推for(inti=2;i<n;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.length==0)return0;// prev 代表 dp[i-2]，curr 代表 dp[i-1]intprev=0;intcurr=0;for(intnum:nums){// 计算当前的 dp[i]inttemp=Math.max(curr,prev+num);// 滚动更新状态prev=curr;curr=temp;}returncurr;}}

五、 复杂度分析
时间复杂度：O(n)。只需遍历一次数组。
空间复杂度：基础版为 O(n)，空间压缩版为 O(1)。