算法题

昨天晚上十一点多,我在公司楼下抽烟,我们组那个老张突然拦住我:哥,这道House Robber咋写啊,我脑壳疼。

我扫了一眼代码,心想这题挺经典的,来,我给你捋一捋。

##算法题：House Robber

题目理解

题目说你是专业小偷,计划偷窃沿街的房屋。

每间房里都有现金,但有个限制:相邻的房屋如果同时被偷,会触发报警。

给你一个数组,代表每个房屋的金额,计算在不触发报警的情况下,能偷到的最高金额。

举例说明:

• 输入 [1,2,3,1],输出 4。偷第1和第3家,1+3=4
• 输入 [2,7,9,3,1],输出 12。偷第1、3、5家,2+9+1=12

说白了就是:选一些数,这些数不能相邻,要让它们的和最大。

思路分析

暴力解法:枚举所有可能的偷窃方案,选金额最大的。每家可以选择偷或不偷,2^n种方案。时间复杂度 O(2^n),空间复杂度 O(n)。n=100时就会超时,这肯定不行。

优化思路 - 动态规划:用 dp[i] 表示偷窃前i家能获得的最大金额。状态转移有两个选择:

1. 偷第i家:那么第i-1家不能偷,就是 dp[i-2] + nums[i]
2. 不偷第i家:那么就是 dp[i-1]

取这两个的最大值:dp[i] = max(dp[i-1], dp[i-2] + nums[i])

时间复杂度 O(n),空间复杂度 O(n)。还可以优化空间到 O(1),因为每次只用到前两个值。

复杂度分析

• 时间复杂度:O(n),其中 n 是房屋数量
• 空间复杂度:O(1),优化后只用常数空间

代码实现

package main

import (
 "fmt"
)

// rob 计算能偷窃到的最高金额
func rob(nums []int) int {
 if len(nums) == 0 {
  return 0
 }
 if len(nums) == 1 {
  return nums[0]
 }

 // prev2表示偷i-2家的最大金额,prev1表示偷i-1家的最大金额
 prev2, prev1 := nums[0], max(nums[0], nums[1])

 for i := 2; i < len(nums); i++ {
  // 当前选择:要么偷这家(prev2+nums[i]),要么不偷这家(prev1)
  current := max(prev1, prev2+nums[i])
  prev2 = prev1
  prev1 = current
 }

 return prev1
}

// max 返回两个数中的较大值
func max(a, b int) int {
 if a > b {
  return a
 }
 return b
}

func main() {
 // 测试用例
 fmt.Println(rob([]int{1, 2, 3, 1}))           // 4
 fmt.Println(rob([]int{2, 7, 9, 3, 1}))      // 12
 fmt.Println(rob([]int{1, 2, 3}))             // 4
 fmt.Println(rob([]int{0}))                    // 0
 fmt.Println(rob([]int{2, 1, 1, 2}))          // 4
 fmt.Println(rob([]int{100, 1, 1, 100}))      // 200
}

注意事项

• 边界条件:数组为空返回0,数组只有1个元素返回这个元素,数组只有2个元素返回较大值。这些边界情况要单独处理。
• 空间优化:一开始可以用 O(n) 的dp数组,但发现每次只用到前两个值,所以优化成 O(1)。prev2对应dp[i-2],prev1对应dp[i-1]。
• 状态转移:dp[i] = max(dp[i-1], dp[i-2] + nums[i])。要么不偷这家(dp[i-1]),要么偷这家(dp[i-2]+nums[i])。这两个选择是互斥的,取最大值。
• 理解题意:相邻的房屋不能同时偷,但可以隔一个偷一个。比如偷1、3、5家,或者2、4、6家。这就是为什么状态转移要考虑i-2而不是i-1。
• Go函数名:函数名叫rob,不是robHouse,面试时要注意函数名的规范。

这题的关键点在于理解动态规划的状态转移。每家有两种选择:偷或不偷。如果偷这一家,上一家就不能偷,所以是dp[i-2]+nums[i]。如果不偷这一家,就是dp[i-1]。取两者最大值就是最优解。