打家劫舍

Tips

题目类型: Dynamic Programming

题目

你是一个专业的小偷, 计划偷窃沿街的房屋. 每间房内都藏有一定的现金, 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入, 系统会自动报警.

给定一个代表每个房屋存放金额的非负整数数组, 计算你不触动警报装置的情况下, 一夜之内能够偷窃到的最高金额.

示例

输入: [1, 2, 3, 1]
输出: 4
解释: 偷窃 1 号房屋(金额 = 1), 然后偷窃 3 号房屋(金额 = 3).
      偷窃到的最高金额 = 1 + 3 = 4.

输入: [2, 7, 9, 3, 1]
输出: 12
解释: 偷窃 1 号房屋(金额 = 2), 偷窃 3 号房屋(金额 = 9), 接着偷窃 5 号房屋(金额 = 1).
      偷窃到的最高金额 = 2 + 9 + 1 = 12.

题解

我们使用两个变量 rob 和 notRob, 其中 rob 表示抢当前的房子, notRob 表示不抢当前的房子.

那么在遍历的过程中, 由于 rob 是要抢当前的房子, 那么前一个房子一定不能抢, 所以使用 notRob 加上当前的数字赋给 rob; notRob 表示不能抢当前的房子, 那么前一个房子可抢可不抢, 所以将 temp 和 notRob 中的较大值赋给 notRob.

参见代码如下.

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const n = nums.length
  if (n === 0) return 0
  if (n === 1) return nums[0]

  let rob = 0,
    notRob = 0

  for (let i = 0; i < n; i++) {
    let temp = rob
    // 如果抢当前的, 那么前一个一定不能抢
    rob = notRob + nums[i]
    // 如果不抢当前的, 那么前一个可抢可不抢, 选价值最高的即可
    notRob = Math.max(temp, notRob)
  }

  return Math.max(rob, notRob)
}

Rust

use std::cmp;

pub fn rob(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n == 0 {
        return 0;
    };
    if n == 1 {
        return nums[0];
    };

    let mut rob = 0;
    let mut not_rob = 0;

    for i in 0..n {
        let temp = rob;
        rob = not_rob + nums[i];
        not_rob = cmp::max(temp, not_rob);
    }

    cmp::max(rob, not_rob)
}