198. House Robber

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

这题很有意思，题目给我们一个数组 nums 表示一排街区每个房子能偷到的钱

如果我们连续偷了相邻的两个房子，会触发报警

题目要求我们在不触发报警的情况下，一晚上最多能偷到多少钱

解题思路

我们假设只有一间房子，我们必须偷，且偷到的钱为 nums[0]

假设有两间房子，我们要选择钱多的偷，偷到的钱为 max(nums[0], nums[1])

假设有三间房子，我们需要判断第三间偷不偷，此时有两种情况：

1. 偷：此时收益为 num[0] + num[2]（我们会错过第二间房子的收益）
2. 不偷：此时收益为 num[1]（我们只能偷第 2 间）

两种情况我们需要取最大值：max(num[0] + num[2], num[1])

我们可以用数组 dp 来保存偷到当前房子的最大收入，dp 的状态转移方程为：

dp[i] = max(dp[i-2] + num[i], dp[i-1])

起始状态为：

• dp[0] = nums[0]
• dp[1] = max(nums[0], nums[1])

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
    const len = nums.length
    const dp = new Array(len).fill(0)
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])

    for (let i = 2; i < len; i++) {
        // we have 2 choices, to rob or not to rob
        // if we rob, then we get dp[i-2] + nums[i]
        // if not, we get dp[i-1]
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
    }

    return dp[len - 1]
};