- 动规五部曲
dp[i]表示在下标为i的房间偷或不偷与前面所偷之和所能获得的最大价值- 递推公式：
dp[i] = std::max(dp[i - 2] + nums[i], dp[i - 1]) - 初始化：要给
dp[0]与dp[1]来给定初始值，因为递推公式有-1与-2。dp[0] = nums[0], dp[1] = std::max(nums[0], nums[1]);
- 其它下标值，初始成任意值都可以，因为其值是由前面元素推导出来的
- 遍历顺序：从2开始到最后一个房间的下标
- 打印
class Solution {
public:
int rob(vector<int>& nums) {
int dp[nums.size()];
memset(dp, 0, sizeof(dp));
if (nums.size() == 1) return nums.at(0);
dp[0] = nums.at(0);
dp[1] = std::max(dp[0], nums.at(1));
for (int i = 2; i < nums.size(); i++) {
dp[i] = std::max(dp[i - 1], dp[i - 2] + nums.at(i));
}
return dp[nums.size() - 1];
}
};
