198. 打家劫舍

题目描述：

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

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

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

---

解题分析及思路：

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 i (i>2) 间房屋，有两个选项：

• 偷窃第 k 间房屋，那么就不能偷窃第 i−1 间房屋，偷窃总金额为前 i−2 间房屋的最高总金额与第 k 间房屋的金额之和。
• 不偷窃第 k 间房屋，偷窃总金额为前 i−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 i 间房屋能偷窃到的最高总金额。

用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：dp[i]=max(dp[i−2]+nums[i],dp[i−1])

边界条件为：

• dp[0]=nums[0] 只有一间房屋，则偷窃该房屋
• dp[1]=max(nums[0],nums[1]) 只有两间房屋，选择其中金额较高的房屋进行偷窃

最终的答案即为 dp[n−1]，其中 n 是数组的长度。

那么对应动态规划解法：

1. 定义状态： 我们定义状态 dp[i] 表示偷窃到第 i 间房屋时的最大金额。

2. 找到状态转移方程： 在每一步，我们有两个选择：偷窃当前房屋或者不偷窃。如果偷窃当前房屋，那么最大金额为 dp[i-2] + nums[i]；如果不偷窃当前房屋，最大金额为 dp[i-1]。因此，状态转移方程为：

dp[i]=max(dp[i−2]+nums[i],dp[i−1])

3. 初始化： 初始化时，我们将第一个房屋的金额作为初始状态，即 dp[0] = nums[0]。

4. 递推求解： 通过状态转移方程，我们逐步求解每个子问题，迭代数组，计算每个位置的最大金额。

5. 计算最终结果： 最终结果为 dp[n-1]，其中 n 为房屋的数量。

实际中，结果集的第i项只与第 i−1 和第 i−2 项有关，并且结果不取决于其他已经遍历过的元素，所以可以将nums数组充当dp数组进行操作，当然你也可以用两个变量来保存。

让我们通过一个简单的例子来说明这个思路：

假设给定房屋金额数组 nums = [2, 7, 9, 3, 1]。

1. 初始化：dp[0] = 2。
2. 对于第二间房屋，有两个选择：偷窃或不偷窃。选择较大者，更新 dp[1] = max(2, 7) = 7。
3. 对于第三间房屋，同样有两个选择：偷窃或不偷窃。选择较大者，更新 dp[2] = max(dp[0] + nums[2], dp[1]) = max(2 + 9, 7) = 11。
4. 依此类推，我们逐步更新 dp 数组。
5. 最终结果为 dp[4]，即 dp[4] = max(dp[3], dp[2] + nums[4])，表示小偷在最后一间房屋时的最大金额。

通过这个思路，我们有效地避免了相邻房屋同时被偷窃的情况，最终得到了一夜之内能够偷窃到的最高金额。

func rob(nums []int) int {
	max := func(i, j int) int {
		if i > j {
			return i
		}
		return j
	}
	for index := range nums {
		if index == 1 {
			nums[index] = max(nums[index], nums[index-1])
		} else if index > 1 {
			nums[index] = max(nums[index-2]+nums[index], nums[index-1])
		}
	}
	return nums[len(nums)-1]
}

复杂度：

• 时间复杂度：O(n)，其中 n 为房屋的数量。只需遍历一次数组。
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:1.9 MB,击败了70.13% 的Go用户