力扣 打家劫舍

题目：

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

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

一、题目理解

给定一个数组nums，其中：

• nums[i]表示第i间房子的金额

• 相邻的房子不能同时抢

目标是：
在不触发警报的前提下，抢到最多的钱。

二、为什么这是动态规划问题？

这是一个**典型的「选择 + 约束」问题：

• 每一间房子只有两种选择：

  • 抢

  • 不抢

• 选择当前房子，会影响后续选择（相邻不能抢）

这种「当前决策依赖之前结果」的结构，非常适合用动态规划（DP）。

三、状态定义（关键）

定义：

dp[i] = 抢到第 i 间房子为止，能够获得的最大金额

注意：

• dp[i] 不是「是否抢第 i 家」

• 而是：在前 i 家房子中，能拿到的最大值

四、状态转移方程（核心）

考虑第i间房子，有两种情况：

情况 1：不抢第 i 间房

那么最大金额等于：dp[i-1]

情况 2：抢第 i 间房

• 那第i-1间房一定不能抢

• 上一个合法状态只能来自i-2

• 那么最大金额等于：dp[i-2] + nums[i]

  class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); if (n == 1) return nums[0]; vector<int> dp(n); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < n; i++) { dp[i] = max(dp[i-1], dp[i-2] + nums[i]); } return dp[n-1]; } };

综合两种情况

dp[i] = max( dp[i-1], dp[i-2] + nums[i] )

这一步是整道题的灵魂

五、初始条件

dp[0] = nums[0] dp[1] = max(nums[0], nums[1])