LeetCode: 198 House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, and the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected, and it will automatically contact the police if two adjacent houses are broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

Example:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9), and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

问题

你是一名职业小偷，计划抢劫沿街的房屋。每间房屋都有一定数量的钱，唯一阻止你抢劫每个房屋的限制是相邻的房屋都有安全系统连接，如果同一晚抢劫两间相邻的房屋，系统会自动联系警察。

给定一个整数数组 nums，表示每个房屋的钱数，返回今晚你在不触发警报的情况下可以抢劫的最大金额。

解决方案

动态规划 (DP)

Approach: Dynamic Programming (Bottom-Up) / 动态规划（自底向上）

This problem can be broken down into smaller subproblems where the decision to rob a house depends on whether it is beneficial to rob the current house or skip it to rob the next one. Using dynamic programming, we can keep track of the maximum amount of money robbed up to each house.

For each house i, we have two choices:

1. Rob the current house: We cannot rob the previous house, so the total is nums[i] + dp[i-2].
2. Skip the current house: We take the amount from the previous house, dp[i-1].

The recurrence relation is:

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

We initialize dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).

Implementation / 实现

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]

        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], nums[i] + dp[i - 2])

        return dp[-1]

Explanation / 解释

1. Base Cases / 基本情况

   if len(nums) == 0:
      return 0
   if len(nums) == 1:
      return nums[0]

   • English: If there are no houses, the maximum amount is 0. If there’s only one house, we rob it.
   • Chinese: 如果没有房子，最大金额为 0。如果只有一间房子，我们就抢劫它。

2. Initialize DP Array / 初始化动态规划数组

   dp = [0] * len(nums)
   dp[0] = nums[0]
   dp[1] = max(nums[0], nums[1])

   • English: We initialize the DP array with the values for the first two houses. dp[0] is the amount of money in the first house, and dp[1] is the maximum between the first and second houses.
   • Chinese: 我们使用前两间房子的值初始化动态规划数组。dp[0] 是第一间房子的金额，dp[1] 是第一间和第二间房子之间的最大值。

3. Iterate Through Houses / 遍历房屋

   for i in range(2, len(nums)):
      dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])

   • English: For each house from the third onward, we update dp[i] as the maximum between robbing the current house and skipping it.
   • Chinese: 对于从第三间房子开始的每间房子，我们更新 dp[i] 为抢劫当前房子和跳过它之间的最大值。

4. Return the Maximum Amount / 返回最大金额

   return dp[-1]

   • English: The last element in the DP array contains the maximum amount of money that can be robbed without triggering the alarm.
   • Chinese: 动态规划数组的最后一个元素包含在不触发警报的情况下可以抢劫的最大金额。

Approach 2: Optimized Dynamic Programming (Space Optimization) / 动态规划优化（空间优化）

We can optimize the space complexity to O(1) by only keeping track of the last two states, as we only need dp[i-1] and dp[i-2] to compute dp[i].

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]

        prev1, prev2 = max(nums[0], nums[1]), nums[0]

        for i in range(2, len(nums)):
            current = max(prev1, nums[i] + prev2)
            prev2 = prev1
            prev1 = current

        return prev1

Explanation / 解释

1. Track the Last Two Values / 跟踪最后两个值

   prev1, prev2 = max(nums[0], nums[1]), nums[0]

   • English: We use two variables prev1 for dp[i-1] and prev2 for dp[i-2] to store the results of the last two houses.
   • Chinese: 我们使用两个变量 prev1 表示 dp[i-1]，prev2 表示 dp[i-2] 来存储最后两间房子的结果。

2. Update in Each Iteration / 每次迭代时更新

   for i in range(2, len(nums)):
      current = max(prev1, nums[i] + prev2)
      prev2 = prev1
      prev1 = current

   • English: For each house, compute the maximum amount by either robbing it or skipping it. Update prev2 and prev1 accordingly.
   • Chinese: 对于每间房子，计算抢劫或跳过它的最大金额。相应更新 prev2 和 prev1。

3. Return the Result / 返回结果

   return prev1

   • English: After the loop completes, prev1 contains the maximum amount that can be robbed.
   • Chinese: 循环结束后，prev1 包含可以抢劫的最大金额。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the number of houses. We process each house once.
• Space Complexity / 空间复杂度:
  • Basic DP: O(n), because we store the maximum values for all houses in a DP array.
  • Optimized DP: O(1), because we only store two variables (prev1 and prev2).

Key Concept / 关键概念

• Dynamic Programming / 动态规划: This problem involves optimizing a decision-making process where each decision depends on previous decisions. By storing the optimal solutions for smaller subproblems, we can efficiently solve the larger problem.
• 动态规划: 这个问题涉及优化决策过程，每个决策取决于之前的决策。通过存储较小子问题的最优解，我们可以高效地解决较大的问题。

Summary / 总结

• English: The House Robber problem can be efficiently solved using dynamic programming by maintaining the maximum money that can be robbed up to each house, with an optimized version using constant space.
• Chinese: 通过动态规划，保持到每间房子为止可以抢劫的最大金额，可以高效地解决

抢劫房屋问题，且优化版本使用常量空间。

Tips / 提示

• English: Practice problems involving dynamic programming and decision-making, especially when solving problems that involve maximizing values while handling constraints (such as skipping adjacent elements).
• Chinese: 练习涉及动态规划和决策的相关问题，特别是解决涉及在处理约束（如跳过相邻元素）的情况下最大化值的问题。

Solution Template for Similar Questions / 提示

• English: For problems involving maximizing values while handling constraints, dynamic programming is often an effective approach. Consider using space optimization techniques to improve your solution.
• Chinese: 对于涉及在处理约束情况下最大化值的问题，动态规划通常是有效的方法。考虑使用空间优化技术来改进你的解决方案。

5 More Similar Questions / 推荐5问题

1. LeetCode 213. House Robber II
2. LeetCode 740. Delete and Earn
3. LeetCode 121. Best Time to Buy and Sell Stock
4. LeetCode 152. Maximum Product Subarray
5. LeetCode 337. House Robber III

Recommended Resources / 推荐资源

• English: Practice problems that involve dynamic programming and optimizing decisions based on constraints to improve your understanding of how to build efficient solutions.
• Chinese: 练习涉及动态规划和基于约束优化决策的问题，以提高你构建高效解决方案的能力。

House Robber – Leetcode 198 – Python Dynamic Programming by NeetCode