动态规划
解题思路
leetcode🧑💻 198. 打家劫舍 的升级版，在 leetcode🧑💻 198. 打家劫舍 的基础上增加了 房间环状排列，则意味着第一间和最后一间不能同时选择，因此可以分成两种情况来讨论，两种情况中取最大值，这样就把环状排列问题转化为了两个单排排列的子问题：
- 偷窃第一间，不偷窃最后一间房间，那么问题转化为偷窃 [0, len - 2] 号房间所能获得的最高金额；
- 偷窃第二间，偷窃最后一间房间，那么问题转化为偷窃 [1, len - 1] 号房间所能获得的最高金额；
确定 dp 数组以及下标的含义：dp[i]：考虑下标 [0, i] 的房屋，最多可以偷窃的金额为 dp[i]
确定递推公式：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])，dp[i] 由两种情况中的最大值转移过来：
- 偷第 i 房间：第 i - 1 房一定是不考虑的，需要偷窃第 i - 2 房，即：最多可以偷窃的金额为 dp[i-2] 加上第 i 房间偷到的钱，则 dp[i] = dp[i - 2] + nums[i]；
- 不偷第 i 房间：可以偷窃第 i - 1 房，则 dp[i] = dp[i - 1]；
如何初始化 dp 数组：
- 递推公式的基础就是 dp[0] 和 dp[1]；
- dp[0] 一定是 nums[0]，dp[1] 就是 nums[0] 和 nums[1] 的最大值；
确定遍历顺序：dp[i] 是根据 dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历；
举例推导 dp 数组：以 [1, 2, 3, 1] 为例：
- 偷窃第一间，不偷窃最后一间房间
第 1 个房间 第 2 个房间 第 3 个房间 第 4 个房间 dp[i] 1 2 40
偷窃第二间，偷窃最后一间房间
第 1 个房间 第 2 个房间 第 3 个房间 第 4 个房间 dp[i] 02 3 3
复杂度
-
时间复杂度：
O(n)，遍历一次数组； -
空间复杂度：
O(n)；
代码实现
var rob = function (nums) {
const len = nums.length
if (len === 1) return nums[0];
// 1. 情况一：偷窃第一间，不偷窃最后一间房间
const result1 = robRange(nums, 0, len - 2);
// 2. 情况二：偷窃第二间，偷窃最后一间房间
const result2 = robRange(nums, 1, len - 1);
// 3. 两种情况中取最大值
return Math.max(result1, result2);
};
const robRange = (nums, start, end) => {
if (end === start) return nums[start];
// 1. 声明 dp 数组
const dp = Array(nums.length).fill(0);
// 2. 初始化 dp 数组
dp[start] = nums[start];
dp[start + 1] = Math.max(nums[start], nums[start + 1]);
// 3. 从第三个房间开始迭代
for (let i = start + 2; i <= end; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[end];
}
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 198. 打家劫舍
上一篇
评论
