一、问题描述

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

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

示例 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 。

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/house-robber

二、方案一：动态规划

1、思路

动态规划的核心思想是：对于每间房屋，有两个选项：偷或不偷。如果我们选择偷这间房屋，那么我们不能偷下一间房屋，因此状态转移方程为 dp[i] = dp[i - 2] + nums[i]；如果我们选择不偷这间房屋，那么我们可以偷下一间房屋，状态转移方程为 dp[i] = dp[i - 1]。我们需要选择这两个选项中能获得的最大金额。

初始化：dp[0] = nums[0]（只有一间房屋时），dp[1] = max(nums[0], nums[1])（有两间房屋时）。

2、代码实现

func rob(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    if n == 1 {
        return nums[0]
    }
    dp := make([]int, n)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i := 2; i < n; i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i])
    }
    return dp[n-1]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组即可。
• 空间复杂度：O(n)，我们需要一个长度为 n 的数组来存储状态。

三、方案二：空间优化动态规划

1、思路

在方案一中，我们使用了一个长度为 n 的数组来存储状态。实际上，我们只需要两个变量来存储前两个状态，因为当前状态只依赖于前两个状态。

2、代码实现

func rob(nums []int) int {
    prev, curr := 0, 0
    for _, num := range nums {
        prev, curr = curr, max(curr, prev+num)
    }
    return curr
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组即可。
• 空间复杂度：O(1)，我们只需要常数级别的额外空间来存储状态。

五、方案三：递归

1、思路

递归方法的基本思想是：对于每间房屋，我们可以选择偷或不偷。如果我们选择偷这间房屋，那么我们不能偷下一间房屋，因此我们需要计算从下下间房屋开始偷能得到的最大金额；如果我们选择不偷这间房屋，那么我们可以偷下一间房屋，因此我们需要计算从下间房屋开始偷能得到的最大金额。我们需要选择这两个选项中能获得的最大金额。 为了优化递归过程，我们可以使用记忆化搜索，即使用一个哈希表来存储已经计算过的状态，避免重复计算。

2、代码实现

func rob(nums []int) int {
    memo := make(map[int]int)
    return helper(0, nums, memo)
}
func helper(i int, nums []int, memo map[int]int) int {
    if i >= len(nums) {
        return 0
    }
    if val, ok := memo[i]; ok {
        return val
    }
    // 偷当前房屋
    steal := nums[i] + helper(i+2, nums, memo)
    // 不偷当前房屋
    notSteal := helper(i+1, nums, memo)
    memo[i] = max(steal, notSteal)
    return memo[i]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。尽管有递归，但由于使用了记忆化搜索，每个状态只计算一次。
• 空间复杂度：O(n)，我们需要一个哈希表来存储已经计算过的状态。

六、总结

方案	时间复杂度	空间复杂度	说明
方案一	O(n)	O(n)	使用数组存储状态
方案二	O(n)	O(1)	使用两个变量存储状态
方案三	O(n)	O(n)	使用递归和记忆化搜索
方案三使用递归和记忆化搜索，虽然时间复杂度与方案一和方案二相同，但空间复杂度较高。在实际应用中，如果数组长度较大，方案二通常更优，因为它只需要常数级别的额外空间。