力扣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

from typing import Listclass Solution:def rob(self, nums: List[int]) -> int:# 如果房屋数量为 0，直接返回 0，因为没有房子可偷if len(nums) == 0:return 0# 如果房屋数量为 1，返回唯一一间房屋的金额if len(nums) == 1:return nums[0]# 如果房屋数量为 2，返回两者中较大的金额if len(nums) == 2:return max(nums[0], nums[1])# 创建一个 dp 数组，其中 dp[i] 表示偷到第 i 间房屋时能获取的最大金额dp = [0] * len(nums)# 初始化前两间房屋的最大偷窃金额dp[0] = nums[0]  # 第一间房屋只能偷它自己dp[1] = max(nums[0], nums[1])  # 第二间房屋可以选择偷第一间或第二间，取金额较大者# 从第 3 间房屋开始，计算每间房屋的最大偷窃金额for i in range(2, len(nums)):# 对于第 i 间房屋，可以选择：# 1. 偷它，并加上偷第 i-2 间房屋的最大金额（因为相邻房屋不能同时偷）# 2. 不偷它，直接取第 i-1 间房屋的最大金额dp[i] = max(dp[i-2] + nums[i], dp[i-1])# 返回最后一间房屋对应的最大偷窃金额，即为结果return dp[-1]

解释：

1. 特殊情况处理：

   • 如果房屋数量为 0，则返回 0，因为没有房屋可以偷。
   • 如果房屋数量为 1，则返回第一个房屋的金额，因为只能偷这一间。
   • 如果房屋数量为 2，则只能偷其中金额较大的一间，因此返回这两者中的最大值。

2. 动态规划数组 dp：

   • dp[i] 代表到达第 i 间房屋时，小偷能偷到的最大金额。
   • 初始化 dp[0] 为第一个房屋的金额，dp[1] 为前两间房屋中金额较大的值。

3. 动态规划递推：

   • 对于每一间房屋，从第 3 间开始（即下标为 2 的房屋），有两种选择：
     1. 偷这一间房屋，加上第 i-2 间房屋的最大金额。
     2. 不偷这一间房屋，取前一间房屋的最大金额。
   • 在这两者中选择较大的值更新 dp[i]，保证每一步都获得最大金额。

4. 结果返回：

   • dp[-1] 即为偷窃到最后一间房屋时的最大金额，也就是最终答案。

dp 是动态规划（Dynamic Programming）的简称，它是一种常见的算法设计思想，用来解决具有重叠子问题和最优子结构的问题。动态规划通过将问题分解为更小的子问题，记录这些子问题的解，然后根据这些子问题的解来构造出原问题的解，从而避免重复计算。

在这个小偷问题中，dp 是一个数组，用来存储每个子问题的最优解，具体来说：

• dp[i] 表示到达第 i 间房屋时，能够偷到的最大金额。这个数组记录了在每个房屋时，如何做出选择（偷还是不偷），使得偷窃的总金额最大。

动态规划的关键概念：

1. 重叠子问题： 动态规划适用于那些可以通过递归或分解为相似的子问题解决的情况。比如，在小偷问题中：

   • 如果你决定偷第 i 间房屋，那么你还需要知道偷第 i-2 间房屋能得到的最大金额（因为相邻的房子不能同时偷）。
   • 如果你不偷第 i 间房屋，那么你只需要知道偷第 i-1 间房屋的最大金额。

2. 最优子结构： 问题的整体最优解可以由其子问题的最优解构成。在这个问题中，偷窃第 i 间房屋的最优解可以通过第 i-2 间房屋和第 i-1 间房屋的最优解推导出来。

举个例子解释 dp 的含义：

假设房屋里的金额是 [2, 7, 9, 3, 1]，小偷希望能偷到最多的钱但不能偷相邻的房子。

• dp[0] = 2：表示只看第 1 间房屋时，最多能偷 2 元。
• dp[1] = 7：表示只看前两间房屋时，最多能偷 7 元（因为第 2 间房屋钱更多，偷第 1 间房屋不划算）。
• dp[2] = max(dp[0] + nums[2], dp[1]) = max(2 + 9, 7) = 11：表示到第 3 间房屋时，可以选择偷第 1 间和第 3 间房屋（共 2 + 9 = 11 元），或者只偷前两间房屋（共 7 元），所以偷第 1 和第 3 间房屋的总金额最大。
• dp[3] = max(dp[1] + nums[3], dp[2]) = max(7 + 3, 11) = 11：到第 4 间房屋时，最优解是保持偷前 3 间房屋的最大金额（11 元），因为偷第 2 间和第 4 间的金额不比之前多。
• dp[4] = max(dp[2] + nums[4], dp[3]) = max(11 + 1, 11) = 12：到第 5 间房屋时，最优解是偷第 1、3、5 间房屋，总金额为 12 元。

动态规划公式：

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

这个公式的意思是，对于每一间房屋 i，你有两个选择：

1. 偷它，然后加上两间前房屋（i-2）的最大偷窃金额。
2. 不偷它，只取前一间房屋（i-1）的最大偷窃金额。

通过这样递推计算，我们可以得出小偷能在不触发警报的情况下，偷窃的最高金额。

总结：

• dp 是动态规划的核心工具，它用于存储每个子问题的最优解。
• 动态规划方法通过分解问题，利用以前的结果，避免了重复计算，使得算法更高效。