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];
        }
    };

提交结果：

本题题解思路来源于：代码随想录