Leetcode 213 House Robber II

2024-03-24 07:48

文章标签 leetcode ii 213 house robber

本文主要是介绍Leetcode 213 House Robber II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
because they are adjacent houses.
Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

中文：
你是个贼，现在让你偷一个条环形排列的房子，要求当前正在作案的房子相邻的房子不能被偷过。现在问你赃款最大可以是多少？

代码：

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==1)return nums.front();if(nums.size()==0)return 0;int* dp1=new int [nums.size()+1];int* dp2=new int [nums.size()+1];memset(dp1,0,sizeof(int)*(nums.size()+1));memset(dp2,0,sizeof(int)*(nums.size()+1));for(int i=0;i<nums.size()-1;i++)//抢第一{if(i>=2)dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i]);else{if(i==0)dp1[i]=nums[i];elsedp1[i]=max(nums[i],dp1[i-1]);}}for(int i=1;i<nums.size();i++){if(i>=3)dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i]);else{if(i==1)dp2[i]=nums[i];elsedp2[i]=max(nums[i],dp2[i-1]);}}return max(dp1[nums.size()-2],dp2[nums.size()-1]);delete [] dp1;delete [] dp2;}
};