213.打家劫舍-ii.md

213.打家劫舍-ii

/*
 * @lc app=leetcode.cn id=213 lang=typescript
 *
 * [213] 打家劫舍 II
 */

// @lc code=start
function rob(nums: number[]): number {}
// @lc code=end

一步步优化的版本 213.打家劫舍-ii

解法 1: 动态规划

• 时间复杂度:
• 空间复杂度:

1. 子问题: 因为房屋围成了一圈,所以第一个和最后一个不能同时偷,可以分成两种情况考虑:
   • 1. 偷第一个屋子,那最后一个就不能偷,这时计算 1~n-1 能偷盗的最高金额
   • 2. 不偷第一个屋子,那最后一个可以偷,这时计算 2~n 能偷盗的最高金额
2. 状态: 分别计算偷第一个和不偷第一个的结果,取最大值
   • i: 表示第 i 间房屋
   • dp[i][0]: 表示不偷第 i 间
   • dp[i][1]: 表示偷第 1 间
3. DP 方程:
   • dp[i][0] = max( dp[i-1][0],dp[i-1][1] )
   • dp[i][1] = dp[i-1][0] + nums[i]
4. 边界:
   • dp[i][0] = 0
   • dp[i][1] = nums[0]

function rob(nums: number[]): number {
  if (nums.length === 1) return nums[0]
  let max = 0
  for (let j = 0; j < 2; j++) {
    const dp = [[0, nums[j]]]
    for (let i = 1; i < nums.length - 1; i++) {
      dp[i] = []
      dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1])
      dp[i][1] = dp[i - 1][0] + nums[i + j]
    }
    max = Math.max(max, dp[dp.length - 1][0], dp[dp.length - 1][1])
  }
  return max
}

优化空间

• 时间复杂度:
• 空间复杂度:

dp[i] 的状态只跟 dp[i-1] 相关,可以使用滚动数组压缩空间,我们直接使用四个变量,在一次循环中完成

function rob(nums: number[]): number {
  let [steal0, nosteal0, steal1, nosteal1] = [nums[0], 0, 0, 0]
  for (let i = 1; i < nums.length; i++) {
    ;[steal1, nosteal1] = [nosteal1 + nums[i], Math.max(steal1, nosteal1)]
    if (i < nums.length - 1) [steal0, nosteal0] = [nosteal0 + nums[i], Math.max(steal0, nosteal0)]
  }
  return Math.max(steal0, nosteal0, steal1, nosteal1)
}

Case

test.each([
  { input: { nums: [2, 3, 2] }, output: 3 },
  { input: { nums: [1, 2, 3, 1] }, output: 4 },
  { input: { nums: [0] }, output: 0 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(rob(nums)).toBe(output)
})