打家劫舍- 间隔差的最大值

[liuyingbin19222]

输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。   偷窃到的最高金额 = 1 + 3 = 4 。

• 利用dp算法，dp方程：dp[n] = max(dp[n-1] , dp[n-2]+num);

  class Solution {
  public:
  int rob(vector<int>& nums) {
      if(nums.size() == 0) return 0;
  
      vector<int> dp(nums.size()+1);
  
      dp[0] = 0;
      dp[1] = nums[0];
  
      for(int i = 2 ;i <= nums.size(); i++){
          dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);    
      }
      return dp[nums.size()];
  }
  };