跳至主要內容

打家劫舍 II

linwu大约 2 分钟

打家劫舍 II

题目描述

给定一个代表每个房屋存放金额的非负整数数组,其中房屋被围成一圈。相邻的房屋在同一晚上被抢会触发警报系统。计算在不触发警报的情况下,你可以在这些房屋中抢劫到的最高金额。

解题步骤

为了计算在不触发警报的情况下能够抢劫到的最高金额,我们可以使用动态规划的思想来解决问题。

  1. 定义状态:我们可以将问题转化为对于每个房屋的状态,即该房屋被抢劫或不被抢劫。令 dp[i] 表示抢劫以第 i 个房屋结尾的子数组所能获得的最高金额。

  2. 初始状态:由于房屋被围成一圈,因此我们需要考虑首尾相连的情况。对于首尾相连的情况,我们有两种选择:

    • 不抢劫第一个房屋,即将问题转化为抢劫第二个房屋到最后一个房屋的子数组,即 dp1[i]
    • 不抢劫最后一个房屋,即将问题转化为抢劫第一个房屋到倒数第二个房屋的子数组,即 dp2[i]
  3. 状态转移方程:对于状态转移,我们可以分别考虑两种情况:

    • 如果抢劫第 i 个房屋,那么前一个房屋不能被抢劫,因此最高金额为 dp[i-2] + nums[i]
    • 如果不抢劫第 i 个房屋,那么最高金额为 dp[i-1]

    综上所述,我们可以得到状态转移方程为 dp[i] = max(dp[i-2] + nums[i], dp[i-1])

  4. 最终解:问题的解即为 max(dp1[n-2], dp2[n-1]),其中 n 是房屋的数量。

下面是使用动态规划解决打家劫舍 II 问题的算法框架:

function rob(nums) {
  const n = nums.length;

  if (n === 0) {
    return 0;
  }

  if (n === 1) {
    return nums[0];
  }

  const dp1 = new Array(n).fill(0);
  const dp2 = new Array(n).fill(0);

  // 计算不抢劫第一个房屋的最高金额
  dp1[0] = 0;
  dp1[1] = nums[1];
  for (let i = 2; i < n; i++) {
    dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1]);
  }

  // 计算不抢劫最后一个房屋的最高金额
  dp2[0] = nums[0];
  dp2[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < n - 1; i++) {
    dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]);
  }

  return Math.max(dp1[n - 2], dp2[n - 2]);
}

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群