重庆推广服务_中国建设工程造价管理系统_北京搜索优化排名公司_百度网站推广关键词怎么查

打家劫舍||

循环数组用拼接数组处理，并多起点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;//返回最大金额}
};