先从最简单的情况入手找规律我们从只有 1 间房、2 间房、3 间房的情况开始一步步推导只有 1 间房[a]没得选只能偷这间最多偷a有 2 间房[a, b]不能同时偷选钱多的那间最多偷max(a, b)有 3 间房[a, b, c]选项 1偷第 3 间房 → 不能偷第 2 间 → 最多偷a c选项 2不偷第 3 间房 → 最多偷前 2 间的最大值max(a, b)所以最多偷max(a c, max(a, b))发现规律了吗对于第 k 间房你只有两个选择偷 或者 不偷取两个选择中钱更多的那个动态规划核心思路一句话讲透用dp[i]表示前 i 间房能偷到的最高金额那么如果偷第 i 间房第 i-1 间房不能偷 → 总金额 dp[i-2] nums[i]如果不偷第 i 间房总金额 dp[i-1]前 i-1 间房的最高金额所以状态转移方程dp[i] max(dp[i-2] nums[i], dp[i-1])1. 处理边界情况如果数组为空没有房屋返回 0如果数组只有 1 个元素只有 1 间房返回这个元素的值2. 初始化 dp 数组dp[0] nums[0]只有第 0 间房最多偷 nums [0]dp[1] max(nums[0], nums[1])有两间房偷钱多的那间3. 遍历数组计算 dp 数组从第 2 间房开始i2一直到最后一间房in-1按照状态转移方程dp[i] max(dp[i-2] nums[i], dp[i-1])计算每一个 dp [i]4. 返回结果dp[n-1]就是前 n 间房能偷到的最高金额class Solution { public: int rob(vectorint nums) { //如果没有房 返回0 if(nums.empty()){ return 0; } //有一个房 int num nums.size(); if(num 1){ return nums[0]; } //数组 vectorint dp(num); dp[0] nums[0]; dp[1] max(nums[0],nums[1]); for(int i 2;inum;i){ dp[i] max(dp[i-2] nums[i],dp[i-1]); } return dp[num-1]; } };