Day21-打家劫舍

📌 题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每个房屋都有一定金额的现金风险，唯一的限制是 不能偷相邻的房子。

给定一个整数数组 nums，其中 nums[i] 是第 i 个房子中的金钱数，返回你在不触发警报的情况下能够偷窃到的 最大金额。

🔍 示例

1
2
3

输入: nums = [1,2,3,1]
输出: 4
解释: 偷窃房屋 1（金额 = 1）和房屋 3（金额 = 3），总金额 = 4。

💡 解题思路

这是一个经典的 动态规划 问题：

定义状态：
dp[i] 表示偷到第 i 间房能获得的最大金额。
状态转移方程：
dp[i] = max(dp[i−1], dp[i−2] + nums[i])
- dp[i−1] 表示不偷第 i 间
- dp[i−2] + nums[i] 表示偷第 i 间
初始条件：
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

时间复杂度：O(n)
空间复杂度：O(1)（滚动优化）

✅ JavaScript 实现

var rob = function(nums) {
    let prevNo = 0, prevYes = 0;
    for (let num of nums) {
        let temp = prevNo;
        prevNo = Math.max(prevNo, prevYes);  // 不偷该房
        prevYes = num + temp;                // 偷该房
    }
    return Math.max(prevNo, prevYes);
};

✅ Swift 实现

func rob(_ nums: [Int]) -> Int {
    var prevNo = 0, prevYes = 0
    for num in nums {
        let temp = prevNo
        prevNo = max(prevNo, prevYes)
        prevYes = num + temp
    }
    return max(prevNo, prevYes)
}

🧠 思考拓展

如何找出被偷的具体房屋下标？
如果房子排列成环，首尾相邻怎么办？（LeetCode 213）
如果每间房有冷却期，需要跳过一段时间再偷，又该如何扩展？（LeetCode 740）