198. 打家劫舍

Origin: LeetCode 198

题目描述

你是一个小偷，沿街排列的房屋中每间都有一定的金额。不能偷相邻的两间房，否则会报警。求能偷到的最大金额。

示例

Input: nums = [1, 2, 3, 1] Output: 4 Explanation: 偷第 1 间（金额 1）和第 3 间（金额 3），共 4。

Input: nums = [2, 7, 9, 3, 1] Output: 12 Explanation: 偷第 1 间（2）+ 第 3 间（9）+ 第 5 间（1）= 12。

约束

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

关键信息

• 不能偷相邻两间
• dp[i] = max(dp[i-1], dp[i-2] + nums[i])
• 可优化为 O(1) 空间（和最大子数组和一样的滚动变量）

Resolution

我的解法

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

解题思路

每间房选偷或不偷：

• 偷：dp[i] = dp[i-2] + nums[i]（前一间不能偷）
• 不偷：dp[i] = dp[i-1]（金额和前一间一样）

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

和最大子数组和一样可以用滚动变量优化到 O(1) 空间，但这里 dp 依赖前两个状态（dp[i-1] 和 dp[i-2]），需要两个变量。

复杂度

• 时间：O(n)
• 空间：O(n)，可优化到 O(1)