慈溪电商网站建设公司_北京注册公司代办多少钱_搜索推广和信息流推广的区别_网络推广工具和方法

思路

1. dp数组定义：考虑0 - i的房屋，不触动报警下，最大金额是dp[i]，在此基础上分为不考虑头和不考虑尾
2. 递推公式：

   dp[i] = max(dp[i-1], dp[i-2]+nums[i]);

   重点是划分成两种情况，由于首尾相连，所以可以不考虑尾或者不考虑首来满足首尾相邻的条件
3. dp数组初始化：

   dp[start] = nums[start];
   dp[start + 1] = max(nums[start], nums[start  + 1]);

4. 遍历顺序：顺序
5. 时间复杂度：     

代码

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