打家劫舍||
循环数组用拼接数组处理，并多起点dp，取所有结果的最大值。
class Solution {
public:
int rob(vector<int>& nums) {
int dp[500] ;
int n=nums.size(); if(n==1)return nums[0];
nums.insert(nums.end(),nums.begin(),nums.end());
//数组倍增一下
int result1=DP(nums,dp,0,n-2);
int result2=DP(nums,dp,1,n-1);
//两种情况，第一种不包括最后一个元素，第二种不包括第一个元素
//因为成环首尾最多偷一个
return max(result1,result2);
//两种情况取最大值
}
int DP(vector<int>&nums,int dp[],int be,int en)
{//be是起点，en是最开始对应的终点
int ant=0;//存最终结果
for(int i=be;i<=en;i++)
{
//循环从不同起点开始，算它的最高金额
memset(dp,0,sizeof(dp));
//重置dp数组
dp[i]=nums[i],dp[i+1]=max(nums[i],nums[i+1]);
//初始化前两个元素，其实这里跟打家劫舍一代码基本没啥区别了
for(int j=i+2;j<=i+en-be;j++)
dp[j]=max(dp[j-2]+nums[j],dp[j-1]);
//当前房子取或不取
//取则+dp[j-2]
//不取则为dp[j-1]
ant=max(ant,dp[i+en-be]);
//取最大金额保存
}
return ant;
//返回最大金额
}
};
