力扣HOT100之动态规划：198. 打家劫舍

这道题之前刷代码随想录的时候做过，这一次直接一遍过了，还是按照动规五部曲：
1.确定dp[i]的含义:将下标为0 ~ i的房子纳入考虑范围时所能取到的最大收益
2.确定递推公式:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
3.dp数组初始化:dp[0] = nums[0], dp[1] = max(nums[0], nums[1]);
4.确定遍历顺序：从左往右遍历
5.打印数组(省略)
这道题的限制是相邻的两个房子不能同时偷，我们在将第0 ~ i间房子纳入考虑范围时，第i间房子只有两种状态：偷或者不偷，如果偷，那么第i - 1间房子就不能偷了，这种情况下的最大收益为dp[i - 2] + nums[i]，如果不偷，那么这种情况下的最大收益为dp[i - 1]，所以我们要取其中的最大值作为dp[i]的值。经过一系列迭代递推，最终的dp[nums.size() - 1]就是我们返回的最终结果。

class Solution {
public:int rob(vector<int>& nums) {//动规五部曲//1.确定dp[i]的含义:将下标为0 ~ i的房子纳入考虑范围时所能取到的最大收益//2.确定递推公式:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);//3.dp数组初始化:dp[0] = nums[0], dp[1] = max(nums[0], nums[1]);//4.确定遍历顺序：从左往右遍历//5.打印数组(省略)int n = nums.size();vector<int> dp(n);dp[0] = nums[0];if(n > 1)dp[1] = max(nums[0], nums[1]);for(int i = 2; i < n; i++)dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);return dp[n - 1];}
};