LeetCode刷题笔记——T0213 打家劫舍Ⅱ

题目描述:

alt

题目思路:

本题属于动态规划题目,考虑到如果只有一户人家,则必偷这户人家可以获得最高金额。由于题目中说到,这个地方的房屋都是围成一圈而建立的,即意味着第一个房屋和最后一个房屋是紧挨着的。所以对房屋进行偷窃时,可以分成两部分进行考虑:第一种情况,只考虑偷窃前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];
        }
    };

提交结果:

alt

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

全部评论

相关推荐

04-15 23:42
中山大学 Java
ResourceUtilization:过几天楼主就会捧着一堆offer来问牛友们该怎么选辣
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务