LCR 090. 打家劫舍 II - 力扣LeetCodeLCR 090. 打家劫舍 II - 一个专业的小偷计划偷窃一个环形街道上沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组 nums 请计算 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 示例 1输入nums [2,3,2]输出3解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。示例 2输入nums [1,2,3,1]输出4解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。 偷窃到的最高金额 1 3 4 。示例 3输入nums [0]输出0 提示 * 1 nums.length 100 * 0 nums[i] 1000 注意本题与主站 213 题相同 https://leetcode.cn/problems/house-robber-ii/ [https://leetcode.cn/problems/house-robber-ii/]https://leetcode.cn/problems/PzWKhm/题目描述你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。思路分析和【打家劫舍 Ⅰ】的区别打家劫舍 Ⅰ 是直线排列的房屋首尾互不影响 本题房屋环形相连第 0 间和最后一间不能同时偷这是核心约束。环形不好直接 DP我们采用拆分思想把环形问题拆成两个线性的【打家劫舍 Ⅰ】子问题情况 1偷第 0 间房子→ 那么最后一间n-1一定不能偷只能在区间[0, n-2]求最大值情况 2不偷第 0 间房子→ 最后一间可偷可不偷在区间[1, n-1]求最大值最终答案 max(情况1结果, 情况2结果)状态定义沿用之前按摩师 / 打家劫舍 Ⅰ 的状态定义保持系列题思路统一fx[i]下标 i 位置偷前 i 个房屋能拿到的最大金额gx[i]下标 i 位置不偷前 i 个房屋能拿到的最大金额class Solution { public: int rob(vectorint nums) { int n nums.size(); if (n 0) return 0; if(n1) return nums[0]; // fx表示该位置接,gx表示该位置不接 vectorint fx(n, 0); vectorint gx(n, 0); // 初始化 // 第0家偷 fx[0] nums[0]; gx[0] 0; for (int i 1; i n; i) { fx[i] nums[i] gx[i - 1]; gx[i] max(fx[i - 1], gx[i - 1]); } int retmax(fx[n - 2], gx[n - 2]); // 第0家不偷 fx[0] 0; gx[0] 0; for (int i 1; i n; i) { fx[i] nums[i] gx[i - 1]; gx[i] max(fx[i - 1], gx[i - 1]); } retmax(max(fx[n - 1], gx[n - 1]),ret); return ret; } };