第一次审完题愣了一下
后来看了 dp[i] 表示可以从 0～i 号房屋偷窃时所能偷窃到的最大金额，然后恍然大悟。这样确定了 dp 数组的含义，然后推到递推公式，确定递归基础。
这道题的官方解答写得很好
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
// dp[i] 的含义是[0,i]号房屋打劫，所能得到的最多金额
vector<int> dp(n);
// 确定递推公式，决定dp[i]的因素就是第i房间偷还是不偷。
// 偷 dp[i] = dp[i-2] + nums[i]
// 不偷 dp[i] = dp[i-1]
// s.t. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
//初始化
if (n == 1) return nums[0];
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i ++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
};
空间压缩
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
// 老实说我感觉这样的倒推不是很实用
// 不如直接处理前面几个特殊情况
int a = 0, b = 0;
for (int i = 0; i < n; i ++) {
nums[i] = max(b, a + nums[i]);
a = b;
b = nums[i];
}
return nums[n - 1];
}
};
[213. 打家劫舍 II](https://qiekn.notion.site/213-II-0bb2119119394b83bce9a85d7473efd6)
[337. 打家劫舍 III](https://qiekn.notion.site/337-III-691e73c252be4e839b4a4f8be6e37c9c)