198. 打家劫舍

  1. dp[i]，虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
  2. 确定递推公式：
    1. dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
  3. 初始化：
    1. dp[0] = nums[0];
    2. dp[1] = max(nums[0], nums[1]);
  4. 确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！
image.png

  1. class Solution {
  2. public:
  3.     int rob(vector<int>& nums) {
  4.         if (nums.size() == 0) return 0;
  5.         if (nums.size() == 1) return nums[0];
  6.         vector<int> dp(nums.size());
  7.         dp[0] = nums[0];
  8.         dp[1] = max(nums[0], nums[1]);
  9.         for (int i = 2; i < nums.size(); i++) {
  10.             dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
  11.         }
  12.         return dp[nums.size() - 1];
  13.     }
  14. };