198. 打家劫舍

[Geekhyt]

原题链接

先明确题意，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警，所以我们得隔着偷。

最优子结构

从 n 个房子中能偷到的最大金额，f(n)。

1. 偷前 n - 1 间房子，最后一间房子不偷
2. 偷前 n - 2 间房子和最后一间房子

状态转移方程

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

处理边界条件

• n = 0，没有房子，所以 dp[0] = 0
• n = 1，只有一个房子，偷就完了，dp[1] = nums[0]

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

降维，空间优化

其实，我们实际上只用到了 f(n - 1) 和 f(n - 2) 的结果，并不需要始终持有整个DP数组，每一步只需要前两个最大值，所以两个变量就足够用了。

const rob = function(nums) {
    const n = nums.length
    if (n === 0) return 0
    let prev = 0
    let curr = 0
    for (let i = 0; i < n; i++) {
        let tmp = curr
        curr = Math.max(curr, prev + nums[i])
        prev = tmp
    }
    return curr
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)