打家劫舍

1. 题目描述

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

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

2. 思路

1. 思路一
   • 奇偶数和并复制最优解
2. 思路二
   • DFS+缓存
   • 偷当前房屋或者不偷当前房屋，取两者最大值

3. 实现

3.1. 奇偶数和并复制最优解

//2 1 1 2
func rob(nums []int) int {
	sumOdd := 0
	sumEven := 0

	for i := 0; i < len(nums); i++ {
		if i%2 == 0 {
			sumEven += nums[i]
			sumEven = Max(sumOdd, sumEven)
		} else
		{
			sumOdd += nums[i]
			sumOdd = Max(sumOdd, sumEven)
		}
	}

	return Max(sumOdd, sumEven)
}

3.2. DFS+缓存

func rob(nums []int) int {
    memo := make(map[int]int, 0)
    return robDFS(nums, 0, memo)
}

func robDFS(nums []int, index int, memo map[int]int) int {
    count, ok := memo[index]
    if ok {
        return count
    }
    if index >= len(nums) {
        return 0
    }

    //偷窃当前住户
    leftCount := nums[index] + robDFS(nums, index+2, memo)
    //不偷窃当前住户
    rightCount := robDFS(nums, index+1, memo)
    //取两者的最大值
    count = max(leftCount, rightCount)
    memo[index] = count
    return count
}

func max(a, b int) int {
    if a > b{
        return a
    }
    return b
}

4. 参考

• 不会动态规划的过来看，记忆化递归，简单易懂 - 打家劫舍 - 力扣（LeetCode）