题目：

题解：

动态规划：

1. 确定dp数组的下标的含义

表示下标i（包括了i）以内的房屋，最多可以偷窃的金额为dp[i]

2. 确定递推公式

决定dp[i]的因素就是第i间房子偷还是不偷

  • 如果偷第i间房子，那么就只能偷第i-2(包括)以前的房子，最多偷窃的金额就是dp[i-2]+第i间房子偷到的钱
  • 如果不偷第i间房子，那么就可以偷第i-1(包括）以前的房子（注意，不一定偷i-1间房子，是在他的前面选一个偷盗的最优解），最多偷盗的金额就是dp[i-1]

那么dp[i]就是两种情况的较大值，即dp[i]=max(dp[i-1],dp[i-2]+nums[i])

3. dp数组的初始化

由递推公式可以看出，递推公式的基础是dp[0]和dp[1]，而dp[0]就是nums[0],dp[1]=max(nums[0],nums[1])

  1. vector<int>dp(nums.size())
  2.     dp[0]=nums[0];
  3.     dp[1]=max(nums[0],nums[1]);

4.确定遍历的顺序

因为dp[i]是根据dp[i-1]和dp[i-2]推导出来的，所以遍历顺序一定是从前到后的遍历

  1. for(int i=2;i<=nums.size();i++)
  2. {
  3.    dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
  4. }

代码呈现：

  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. };