213. 打家劫舍 II

🟠   🔖  数组 动态规划  🔗 力扣 LeetCode

题目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonightwithout alerting the police.

Example 1:

Input: nums = [2,3,2]

Output: 3

Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [1,2,3]

Output: 3

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

题目大意

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 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 = [1,2,3]

输出： 3

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

解题思路

这道题目是经典的“打家劫舍”问题的环形变种：在一个环形街区，房子排列成一个环，要求计算能够偷窃到的最高金额。由于房屋是环形排列，不能同时偷第一个房子和最后一个房子。

1. 环形问题拆解：

   • 如果偷了第一个房子，那么最后一个房子不能偷，问题变为从第一个房子到倒数第二个房子的线性“打家劫舍”问题。
   • 如果不偷第一个房子，那么可以从第二个房子到最后一个房子进行线性“打家劫舍”。

2. 动态规划：

   • 设 dp[i] 表示偷窃到第 i 个房子时的最高金额。

   • 转移方程为：

     dp[i] = max(dp[i-1], dp[i-2] + nums[i])

     • dp[i-1]：不偷第 i 个房子，取前一个房子的最大金额。
     • dp[i-2] + nums[i]：偷第 i 个房子，则前 i-1 个房子不能偷，取前 i-2 个房子的最大金额加上第 i 个房子的金额。

   • 初始化：

     • dp[0] = nums[0]
     • dp[1] = max(nums[0], nums[1])

3. 两个独立的子问题：

   • 子问题 1：求解从第一个房子到倒数第二个房子的最高金额。
   • 子问题 2：求解从第二个房子到最后一个房子的最高金额。

4. 最终结果：

   • 返回两个子问题的最大值：result = max(subproblem1, subproblem2)

复杂度分析

• 时间复杂度：O(n)，每个子问题遍历一次数组，总共两次遍历。
• 空间复杂度：O(1)，使用常数级变量存储中间结果。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
	const n = nums.length;
	if (n === 1) return nums[0];

	// 动态规划，解决线性问题
	const robLinear = (nums, start, end) => {
		let prev2 = 0,
			prev1 = 0;
		for (let i = start; i <= end; i++) {
			const cur = Math.max(prev1, prev2 + nums[i]);
			prev2 = prev1;
			prev1 = cur;
		}
		return prev1;
	};

	// 分别计算两个子问题
	const case1 = robLinear(nums, 0, n - 2); // 偷第一个房子
	const case2 = robLinear(nums, 1, n - 1); // 不偷第一个房子

	return Math.max(case1, case2);
};

相关题目

题号	标题	题解	标签	难度	力扣
198	打家劫舍	[✓]	数组 动态规划	🟠	🀄️ 🔗
256	粉刷房子 🔒		数组 动态规划	🟠	🀄️ 🔗
276	栅栏涂色 🔒		动态规划	🟠	🀄️ 🔗
337	打家劫舍 III	[✓]	树 深度优先搜索 动态规划 1+	🟠	🀄️ 🔗
600	不含连续1的非负整数		动态规划	🔴	🀄️ 🔗
656	成本最小路径 🔒		数组 动态规划	🔴	🀄️ 🔗