求SDE岗位DP相关编程题的解题思路

Hey there! Let's break down a super common DP problem that's often asked in SDE interviews—House Robber—since it fits the bill perfectly. I'll walk you through the problem description, input/output specs, test cases, and step-by-step DP solution.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, 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 were 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.

• Input: A non-empty integer array nums where each element nums[i] is the amount of money in the i-th house (0 ≤ nums[i] ≤ 400). The length of nums can range from 1 to 100.
• Output: An integer representing the maximum sum of money you can rob without triggering the alarm.

Let's look at a few test cases to solidify understanding:

• Test Case 1:
  • Input: nums = [1,2,3,1]
  • Output: 4
  • Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total is 1 + 3 = 4.
• Test Case 2:
  • Input: nums = [2,7,9,3,1]
  • Output: 12
  • Explanation: Rob house 1 (2), house 3 (9), and house 5 (1). Total is 2 + 9 + 1 = 12.
• Test Case 3:
  • Input: nums = [2,1,1,2]
  • Output: 4
  • Explanation: Rob house 1 (2) and house 4 (2). Total is 4.

Step 1: Define the DP State #

Let dp[i] represent the maximum amount of money we can rob up to the i-th house (0-indexed).

Step 2: State Transition #

For each house i, we have two choices:

1. Don't rob the i-th house: Then dp[i] = dp[i-1] (we take the maximum from the previous house).
2. Rob the i-th house: Then we can't rob the (i-1)-th house, so dp[i] = dp[i-2] + nums[i] (we take the max up to i-2 plus the current house's money).

So the transition equation is:
dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Step 3: Base Cases #

• If there's only 1 house: dp[0] = nums[0]
• If there are 2 houses: dp[1] = max(nums[0], nums[1])

Step 4: Optimize Space (Optional) #

We don't need to store the entire DP array—since we only need the previous two values. We can use two variables, prev_prev and prev, to track dp[i-2] and dp[i-1] respectively. This reduces the space complexity from O(n) to O(1).

Code Implementation (Python) #

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    prev_prev = nums[0]
    prev = max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        current = max(prev, prev_prev + nums[i])
        prev_prev, prev = prev, current
    
    return prev

Explanation of the Code #

• We handle edge cases first (empty array or single house).
• Initialize prev_prev and prev to cover the first two houses.
• Iterate from the third house onwards: calculate the current maximum by choosing between robbing the current house (adding to prev_prev) or skipping it (keeping prev).
• Update the tracking variables and return the final prev value, which holds the maximum amount for the entire array.

内容的提问来源于stack exchange，提问作者thebeast