LeetCode - #198 打家劫舍

  大家好，我是 展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》
图书作者：《SwiftUI 入门，进阶与实战》
超级个体：COC上海社区主理人
特约讲师：大学讲师，谷歌亚马逊分享嘉宾
科技博主：极星会首批签约作者

摘要

本文将介绍如何用 动态规划（Dynamic Programming, DP） 解决经典的 “打家劫舍”（House Robber） 问题。我们将提供 Swift 代码实现，并对其进行详细分析，包括时间复杂度、空间复杂度、代码逻辑解析，以及可运行的测试示例。

描述

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

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

示例 1：

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

示例 2：

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

提示：

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

题解答案

这个问题适合使用 动态规划（DP） 来解决。我们定义：

• dp[i]：表示 前 i 间房屋 能偷窃到的最大金额。

状态转移方程：

• 偷当前房屋（i）：dp[i] = nums[i] + dp[i-2]
• 不偷当前房屋（i）：dp[i] = dp[i-1]
• 取两者较大值：dp[i] = max(dp[i-1], nums[i] + dp[i-2])

初始化条件：

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

Swift 代码实现

import Foundation

func rob(_ nums: [Int]) -> Int {
    let n = nums.count
    if n == 0 { return 0 }
    if n == 1 { return nums[0] }
    
    var dp = Array(repeating: 0, count: n)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in 2..<n {
        dp[i] = max(dp[i-1], nums[i] + dp[i-2])
    }
    
    return dp[n-1]
}

// 示例测试
let houses1 = [1,2,3,1]
let houses2 = [2,7,9,3,1]

print(rob(houses1))  // 输出: 4
print(rob(houses2))  // 输出: 12

题解代码分析

1. 定义动态规划数组 dp[i]，记录偷窃前 i 间房屋能得到的最高金额。
2. 初始化边界值：
   • dp[0] = nums[0]，即如果只有一间房，则只能偷它的金额。
   • dp[1] = max(nums[0], nums[1])，如果有两间房，只能偷金额较大的那一间。
3. 状态转移：
   • 不偷当前房屋：金额和前一个房屋相同 dp[i] = dp[i-1]
   • 偷当前房屋：金额等于当前房屋的钱 nums[i] 加上 dp[i-2]
   • 取两者最大值：dp[i] = max(dp[i-1], nums[i] + dp[i-2])
4. 返回最终结果 dp[n-1]。

示例测试及结果

输入：

let houses = [2,7,9,3,1]
print(rob(houses))

输出：

12

时间复杂度

• 遍历 nums 一次，每个元素进行 O(1) 操作，因此时间复杂度为 O(n)。

空间复杂度

• 由于使用了 dp 数组存储 n 个元素，空间复杂度为 O(n)。
• 优化方案：只用两个变量 prev1 和 prev2 代替 dp 数组，可以将空间复杂度降为 O(1)。

优化代码：

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

总结

1. 解法：

   • 动态规划，状态 dp[i] = max(dp[i-1], nums[i] + dp[i-2])
   • 优化：用 prev1 和 prev2 变量代替数组，节省 O(n) 的空间。

2. 时间复杂度：

   • O(n)，因为只遍历了一次数组。

3. 空间复杂度：

   • 标准解法：O(n)
   • 优化解法：O(1)

4. 适用场景：

   • 适用于序列优化问题，比如游戏关卡最优选择、投资最优策略等。