198.打家劫舍

链接：198.打家劫舍
难度：Medium
标签：数组、动态规划
简介：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

题解 1 - typescript

• 编辑时间：2020-04-22
• 执行用时：68ms
• 内存消耗：32.4MB
• 编程语言：typescript
• 解法介绍：dp[i]=Math.max(dp[i-2]+nums[i],dp[i+1]);。

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

题解 2 - typescript

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

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

题解 3 - typescript

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

function rob(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(0).map(_ => new Array(2).fill(0));
  dp[0][1] = nums[0];
  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(...dp[i - 1]);
    dp[i][1] = dp[i - 1][0] + nums[i];
  }
  return Math.max(...dp[n - 1]);
}

题解 4 - cpp

• 编辑时间：2023-09-16
• 执行用时：4ms
• 内存消耗：8.1MB
• 编程语言：cpp
• 解法介绍：dp记录当前下标下的最大值。

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

题解 5 - python

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

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

题解 6 - rust

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

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