LeetCode刷题笔记——T0213 打家劫舍Ⅱ
题目描述:
题目思路:
本题属于动态规划题目,考虑到如果只有一户人家,则必偷这户人家可以获得最高金额。由于题目中说到,这个地方的房屋都是围成一圈而建立的,即意味着第一个房屋和最后一个房屋是紧挨着的。所以对房屋进行偷窃时,可以分成两部分进行考虑:第一种情况,只考虑偷窃前nums.size()-1户人家;第二种情况,只考虑偷窃后nums.size()-1户人家。然后对于两种情况选择最大值,这样是不会触发警报的。对于这两种情况的考虑,则问题回归成了题目:T0198 打家劫舍。
代码如下:
class Solution {
public:
int rob(vector<int>& nums) {
//若只有一户人家,必偷这家
if (nums.size() == 1)
return nums[0];
//考虑首元素 robRange(nums, 0, nums.size() - 2)
//考虑尾元素 robRange(nums, 1, nums.size() - 1)
return max(robRange(nums, 0, nums.size() - 2), robRange(nums, 1, nums.size() - 1));
}
int robRange(vector<int>& nums, int startIndex, int stopIndex) {
if (startIndex == stopIndex)
return nums[startIndex];
vector<int> dp(stopIndex - startIndex + 1, 0);
dp[0] = nums[startIndex];
dp[1] = max(nums[startIndex], nums[startIndex + 1]);
for (int i = startIndex + 2; i <= stopIndex; ++i) {
dp[i - startIndex] = max(dp[i - startIndex - 2] + nums[i], dp[i - startIndex - 1]);
}
return dp[dp.size() - 1];
}
};
提交结果:
本题题解思路来源于:代码随想录