213.打家劫舍II

链接：213.打家劫舍II
难度：Medium
标签：数组、动态规划
简介：给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

题解 1 - typescript

• 编辑时间：2021-04-15
• 执行用时：108ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：动态规划，考虑到头尾相接，分别考虑第一个偷和不偷的情况。

function rob(nums: number[]): number {
  const size = nums.length;
  if (size === 1) return nums[0];
  let max = 0;
  const dp: number[][] = new Array(size).fill(0).map(_ => new Array(2));
  const traversal = () => {
    for (let i = 1; i < size; i++) {
      dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
      dp[i][1] = dp[i - 1][0] + nums[i];
    }
  };
  // 第一个不偷
  dp[0][0] = 0;
  dp[0][1] = 0;
  traversal();
  max = Math.max(dp[size - 1][0], dp[size - 1][1]);
  // 第一个偷
  dp[0][1] = nums[0];
  traversal();
  max = Math.max(max, dp[size - 1][0]);
  return max;
}

题解 2 - typescript

• 编辑时间：2021-09-13
• 执行用时：84ms
• 内存消耗：41.5MB
• 编程语言：typescript
• 解法介绍：动态规划。

function rob(nums: number[]): number {
  const n = nums.length;
  if (n < 3) return Math.max(...nums);
  /**
   * 0 => 偷
   * 1 => 不偷
   * dp(i,j,k) = 第i个房子是否偷(j)且第一个房子是否偷(k)
   */
  const dp = new Array(n).fill(0).map(_ => new Array(2).fill(0).map(_ => new Array(2).fill(0)));
  dp[0][0][0] = nums[0];
  dp[1][0][1] = nums[1];
  dp[1][1][0] = nums[0];
  for (let i = 2; i < n; i++) {
    dp[i][0][0] = Math.max(Math.max(dp[i - 2][0][0], dp[i - 2][1][0]) + nums[i], dp[i - 1][1][0]);
    dp[i][0][1] = Math.max(Math.max(dp[i - 2][0][1], dp[i - 2][1][1]) + nums[i], dp[i - 1][1][1]);
    dp[i][1][0] = Math.max(dp[i - 1][0][0], dp[i - 1][1][0]);
    dp[i][1][1] = dp[i - 1][0][1];
  }
  return Math.max(dp[n - 1][0][1], dp[n - 1][1][0], dp[n - 1][1][1]);
}

题解 3 - typescript

• 编辑时间：2021-09-13
• 执行用时：84ms
• 内存消耗：40.3MB
• 编程语言：typescript
• 解法介绍：动态规划优化。

function rob(nums: number[]): number {
  const n = nums.length;
  if (n < 3) return Math.max(...nums);
  /**
   * 0 => 偷
   * 1 => 不偷
   * dp(i,j,k) = 第i个房子是否偷(j)且第一个房子是否偷(k)
   */
  const dp = new Array(3).fill(0).map(_ => new Array(2).fill(0).map(_ => new Array(2).fill(0)));
  dp[0][0][0] = nums[0];
  dp[1][0][1] = nums[1];
  dp[1][1][0] = nums[0];
  for (let i = 2; i < n; i++) {
    const idx = i % 3;
    const prevIdx = (i - 1) % 3;
    const prevIdx2 = (i - 2) % 3;
    dp[idx][0][0] = Math.max(
      Math.max(dp[prevIdx2][0][0], dp[prevIdx2][1][0]) + nums[i],
      dp[prevIdx][1][0]
    );
    dp[idx][0][1] = Math.max(
      Math.max(dp[prevIdx2][0][1], dp[prevIdx2][1][1]) + nums[i],
      dp[prevIdx][1][1]
    );
    dp[idx][1][0] = Math.max(dp[prevIdx][0][0], dp[prevIdx][1][0]);
    dp[idx][1][1] = dp[prevIdx][0][1];
    console.log(i, dp);
  }
  const lastIdx = (n - 1) % 3;
  return Math.max(dp[lastIdx][0][1], dp[lastIdx][1][0], dp[lastIdx][1][1]);
}

题解 4 - cpp

• 编辑时间：2023-09-17
• 内存消耗：8.26MB
• 编程语言：cpp
• 解法介绍：dp[0][j]表示首个不选的时候最大值，dp[1][j]表示首个选的时候最大值。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(2, 0));
        dp[1][1] = nums[0];
        int res = nums[0];
        for (int i = 2; i < n + 1; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 2][0] + nums[i - 1]);
            if (i != n)  dp[i][1] = max(dp[i - 1][1], dp[i - 2][1] + nums[i - 1]);
            res = max(res, max(dp[i][0], dp[i][1]));
        }
        return res;
    }
};

题解 5 - python

• 编辑时间：2023-09-17
• 执行用时：32ms
• 内存消耗：15.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0, 0] for _ in range(n + 1)]
        dp[1][1] = nums[0]
        res = nums[0]
        for i in range(2, n + 1):
            dp[i][0] = max(dp[i - 1][0], dp[i - 2][0] + nums[i - 1])
            if i != n:
                dp[i][1] = max(dp[i - 1][1], dp[i - 2][1] + nums[i - 1])
            res = max(res, dp[i][0], dp[i][1])
        return res

题解 6 - rust

• 编辑时间：2023-09-17
• 内存消耗：1.93MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut dp = vec![vec![0; 2]; n + 1];
        dp[1][1] = nums[0];
        let mut res = nums[0];
        for i in 2..n + 1 {
            dp[i][0] = dp[i - 1][0].max(dp[i - 2][0] + nums[i - 1]);
            if i != n {
                dp[i][1] = dp[i - 1][1].max(dp[i - 2][1] + nums[i - 1]);
            }
            res = res.max(dp[i][0].max(dp[i][1]))
        }
        res
    }
}