本文主要是介绍每日一题(力扣213)：打家劫舍2--dp+分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
与打家劫舍1不同的是它最后一个和第一个会相邻，事实上，从结果思考，最后只会有三种：1 第一家不被抢 最后一家被抢 2 第一家被抢 最后一家不被抢 3 第一和最后一家都不被抢 。那么，根据打家劫舍1中的算法 我们能算出在i到j房子区间内能抢到的最大金额，那我们可以考虑计算两路 1 从1 到 n-1的结果 和 从 2 到 n的结果 ，最后取两者的最大即可。（第一家和最后一家都没被抢的情况实际可以包括在两种情况的任意一种中）
class Solution {
public:int rob(vector<int>& nums) {int n=nums.size();if(n==1) return nums[0];if(n==2) return max(nums[0],nums[1]);vector<int> dp1(n,0);vector<int> dp2(n,0);dp1[1]=nums[1];dp1[2]=max(nums[1],nums[2]);for(int i=3;i<n;i++){dp1[i]=max(dp1[i-2]+nums[i],dp1[i-1]);}dp2[0]=nums[0];dp2[1]=max(nums[0],nums[1]);for(int i=2;i<n-1;i++){dp2[i]=max(dp2[i-2]+nums[i],dp2[i-1]);}return max(dp1[n-1],dp2[n-2]);}
};这篇关于每日一题(力扣213)：打家劫舍2--dp+分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
