1、思路
-
此题与上一题 剑指 Offer II 089:房屋偷盗(DP)类似,唯一不同的条件是房屋排列呈环状;
-
偷了第一家就不能偷最后一家,偷了最后一家就不能偷第一家,所以分两种情况讨论:
1、计算标号为0
到标号为n - 2
的房屋能偷到的最大值
2、计算标号为1
到标号为n - 1
的房屋能偷到的最大值,取两者的最大值即可。
2、代码
class Solution {
public:
int getMaxVal(vector<int> nums, int st, int ed) //将上一题的方法独立出来
{
nums[st + 1] = max(nums[st], nums[st + 1]);
for (int i = st + 2; i <= ed; ++ i)
{
nums[i] = max(nums[i] + nums[i - 2], nums[i - 1]);
}
return nums[ed];
}
int rob(vector<int>& nums) {
if (nums.size() <= 2) return nums.size() == 1 ? nums[0] : max(nums[0], nums[1]);
//两种情况取最大值
return max(getMaxVal(nums, 0, nums.size() - 2), getMaxVal(nums, 1, nums.size() - 1));
}
};