代码随想录：打家劫舍||

打家劫舍||

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

原文地址：https://blog.csdn.net/qq_74924951/article/details/142371734

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！