题目链接：
本题考察动态规划。
实现一、递推
\(f[i]\) 表示考虑下标从 \(0 \sim i\) 的房屋最多能抢劫到的金额。
思考状态转移时考虑第 \(i\) 个房屋抢或不抢。
由于不能抢劫相邻的房屋，若抢了第 \(i\) 个房屋，则第 \(i-1\) 个房屋就不能抢，再抢只能从 \(i-2\) 开始考虑，即 \(\rm f[i-2]+nums[i]\)。若不抢第 \(i\) 个房屋，则从 \(i-1\) 开始考虑，即 \(\rm f[i-1]\)。
class Solution {
public:
static const int N = 110;
int f[N];
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);//由于房屋个数未知，而状态转移时会用到i-2，i从2开始循环迭代，因此需要特判一下~
f[0] = nums[0];
f[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
f[i] = max(f[i - 2] + nums[i], f[i - 1]);
}
return f[n - 1];
}
};
若不想特判，使得代码看起来更加简洁，可以考虑把 \(f\) 数组的每个下标值都加上 \(2\)。
class Solution {
public:
static const int N = 110;
int f[N];
int rob(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
f[i + 2] = max(f[i + 1], f[i] + nums[i]);
}
return f[n + 1];
}
};
实现二、记忆化搜索
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> memo(n, -1);//-1表示没有计算过
//dfs(i)表示从nums[0]到nums[i]最多能偷多少
function<int(int)> dfs = [&] (int i) -> int {
if (i < 0) return 0;//递归边界（没有房子）
if (memo[i] != -1) return memo[i];//之前计算过
return memo[i] = max(dfs(i - 1), dfs(i - 2) + nums[i]);
};
return dfs(n - 1);//一直到最后一个房子
}
};