【力扣100题】43.打家劫舍

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 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

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

解题思路总览

核心原理：偷到第 i 间房时，最大收益 = max(偷第 i 间：dp[i-2] + nums[i]，不偷第 i 间：dp[i-1])

方法一：动态规划（推荐）

思路

经典的房间 DP 问题：

1. 状态定义：dp[i]表示偷到第 i 间房（0-indexed）时能获取的最高金额
2. 状态转移：
   • 偷第 i 间房：不能偷 i-1 间，所以最大收益是dp[i-2] + nums[i]
   • 不偷第 i 间房：最大收益是dp[i-1]
   • dp[i] = max(dp[i-2] + nums[i], dp[i-1])
3. 初始化：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])
4. 空间优化：只需要前两个状态，用变量滚动

完整代码

classSolution{public:introb(vector<int>&nums){if(nums.size()==0)return0;intn=nums.size();if(n==1)returnnums[0];vector<int>dp(n,0);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(inti=2;i<n;i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}returndp[n-1];}};

算法流程图

以nums = [2,7,9,3,1]为例：

初始： dp[0] = 2 dp[1] = max(2, 7) = 7 i = 2: dp[2] = max(dp[0] + nums[2], dp[1]) = max(2 + 9, 7) = max(11, 7) = 11 说明：偷第2间房（9）收益更高 i = 3: dp[3] = max(dp[1] + nums[3], dp[2]) = max(7 + 3, 11) = max(10, 11) = 11 说明：不偷第3间房，保留之前的11 i = 4: dp[4] = max(dp[2] + nums[4], dp[3]) = max(11 + 1, 11) = max(12, 11) = 12 说明：偷第4间房得到最高收益12 最终 dp[4] = 12 偷窃方案：房间0(2) + 房间2(9) + 房间4(1) = 12

逐行解析

if(nums.size()==0)return0;

• 空数组返回 0。

intn=nums.size();if(n==1)returnnums[0];

• 只有一间房，直接返回。

vector<int>dp(n,0);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);

• 初始化：
  • dp[0] = nums[0]，只有一间房只能偷它
  • dp[1] = max(nums[0], nums[1])，两间房不能同时偷，选金额大的

for(inti=2;i<n;i++){dp[i]=max(dp[i-2]+nums[i],dp[i-1]);}

• 核心状态转移：
  • dp[i-2] + nums[i]：偷第 i 间房，加上之前偷到 i-2 的最大收益
  • dp[i-1]：不偷第 i 间房，保留之前的最大收益
  • 取两者的最大值

returndp[n-1];

• 返回最后一间房的 dp 值，即全局最大收益。

复杂度分析

优点：状态转移清晰，空间可优化
缺点：无

空间优化版本

思路

只需要保存前两个状态，将空间复杂度降到 O(1)。

完整代码

classSolution{public:introb(vector<int>&nums){if(nums.empty())return0;intn=nums.size();if(n==1)returnnums[0];intprev2=nums[0];// dp[i-2]intprev1=max(nums[0],nums[1]);// dp[i-1]for(inti=2;i<n;i++){intcur=max(prev2+nums[i],prev1);// dp[i]prev2=prev1;prev1=cur;}returnprev1;}};

逐行解析

intprev2=nums[0];// dp[i-2]intprev1=max(nums[0],nums[1]);// dp[i-1]

• prev2存储dp[i-2]
• prev1存储dp[i-1]

for(inti=2;i<n;i++){intcur=max(prev2+nums[i],prev1);// dp[i]prev2=prev1;prev1=cur;}

• 计算当前dp[i]
• 更新prev2 = prev1（dp[i-1] 变成下一轮的 dp[i-2]）
• 更新prev1 = cur（dp[i] 变成下一轮的 dp[i-1]）

复杂度分析

两种方法对比

面试追问 FAQ

相关题目

总结