力扣第198题“打家劫舍”

关注微信公众号 数据分析螺丝钉 免费领取价值万元的python/java/商业分析/数据结构与算法学习资料

在本篇文章中，我们将详细解读力扣第198题“打家劫舍”。通过学习本篇文章，读者将掌握如何使用动态规划来解决这一问题，并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释，以便于理解。

问题描述

力扣第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. 初步分析：

   • 我们可以使用动态规划来解决这个问题。
   • 定义 dp[i] 为前 i 间房屋能偷窃到的最高金额。
   • 每间房屋有两个选择：偷窃或不偷窃。如果偷窃第 i 间房屋，那么第 i-1 间房屋不能偷窃；如果不偷窃第 i 间房屋，那么第 i-1 间房屋可以偷窃。

2. 状态转移方程：

   • dp[i] = max(dp[i-1], dp[i-2] + nums[i])
   • 其中，dp[i-1] 表示不偷窃第 i 间房屋的最高金额，dp[i-2] + nums[i] 表示偷窃第 i 间房屋的最高金额。

3. 边界条件：

   • dp[0] = nums[0]
   • dp[1] = max(nums[0], nums[1])

代码实现

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    if len(nums) == 2:
        return max(nums[0], nums[1])
    
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[-1]

# 测试案例
print(rob([1,2,3,1]))  # 输出: 4
print(rob([2,7,9,3,1]))  # 输出: 12

复杂度分析

• 时间复杂度：O(n)，其中 n 是房屋的数量。我们只需要遍历一次数组。
• 空间复杂度：O(n)，用于存储动态规划数组。

模拟面试问答

问题 1：你能描述一下如何解决这个问题的思路吗？

回答：我们可以使用动态规划来解决这个问题。定义 dp[i] 为前 i 间房屋能偷窃到的最高金额。每间房屋有两个选择：偷窃或不偷窃。如果偷窃第 i 间房屋，那么第 i-1 间房屋不能偷窃；如果不偷窃第 i 间房屋，那么第 i-1 间房屋可以偷窃。

问题 2：为什么选择使用动态规划来解决这个问题？

回答：动态规划是一种解决最优子结构问题的有效方法。在这个问题中，每间房屋的决策（偷窃或不偷窃）都依赖于之前房屋的决策，因此可以通过动态规划来找到最优解。

问题 3：你的算法的时间复杂度和空间复杂度是多少？

回答：算法的时间复杂度为 O(n)，其中 n 是房屋的数量。我们只需要遍历一次数组。空间复杂度为 O(n)，用于存储动态规划数组。

问题 4：在代码中如何处理只有一间或两间房屋的情况？

回答：如果只有一间房屋，直接返回该房屋的金额。如果有两间房屋，返回两者中金额较大的一个。通过这种方式，可以处理边界情况。

问题 5：你能解释一下动态规划的状态转移方程吗？

回答：动态规划的状态转移方程为 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。其中，dp[i-1] 表示不偷窃第 i 间房屋的最高金额，dp[i-2] + nums[i] 表示偷窃第 i 间房屋的最高金额。

问题 6：在代码中如何确保返回的结果是正确的？

回答：通过定义动态规划数组 dp，并使用状态转移方程计算每间房屋的最高金额，最后返回 dp 数组的最后一个元素，即为最高金额。通过这种方式，可以确保返回的结果是正确的。

问题 7：你能举例说明在面试中如何回答优化问题吗？

回答：在面试中，如果面试官问到如何优化算法，我会首先分析当前算法的瓶颈，如时间复杂度和空间复杂度，然后提出优化方案。例如，对于动态规划的问题，可以通过优化空间复杂度，将 dp 数组的长度减少到两个元素，从而节省空间。解释其原理和优势，最后提供优化后的代码实现。

问题 8：如何验证代码的正确性？

回答：通过运行代码并查看结果，验证返回的金额是否为最高金额。可以使用多组测试数据，包括正常情况和边界情况，确保代码在各种情况下都能正确运行。例如，可以在测试数据中包含多个房屋和金额，确保代码结果正确。

问题 9：你能解释一下解决打家劫舍问题的重要性吗？

回答：解决打家劫舍问题在实际生活中具有一定的启发意义。通过分析最优解，可以帮助我们在面临类似决策问题时，找到最优策略。在计算机科学中，动态规划是解决最优子结构问题的重要方法，通过学习和应用动态规划，可以提高解决问题的能力。

问题 10：在处理大数据集时，算法的性能如何？

回答：算法的性能取决于房屋的数量。在处理大数据集时，通过优化空间复杂度，可以显著提高算法的性能。例如，通过将 dp 数组的长度减少到两个元素，可以节省大量空间，从而提高算法的效率。

总结

本文详细解读了力扣第198题“打家劫舍”，通过使用动态规划高效地解决了这一问题，并提供了详细的解释和模拟面试问答。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。