Interview Bootcamp

0% completed

​

Solution: House thief

There are n houses built in a line. A thief wants to steal the maximum possible money from these houses. The only restriction the thief has is that he can't steal from two consecutive houses, as that would alert the security system. How should the thief maximize his stealing?

Problem Statement

Given a number array representing the wealth of n houses, determine the maximum amount of money the thief can steal without alerting the security system.

Example 1:

Input: {2, 5, 1, 3, 6, 2, 4}
Output: 15
Explanation: The thief should steal from houses 5 + 6 + 4

Example 2: ``

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findMaxSteal(self, wealth):
    
    def dp(index, acc, skip, memo):
      
      if (index, acc, skip) in memo:
        return memo[(index, acc, skip)]

      if index == len(wealth):
        return acc
        
      if index > len(wealth):
        return 0

      result = 0
      if not skip:
        with_house = dp(index + 1, wealth[index] + acc, True, memo) 
        without_house = dp(index + 1, acc, False, memo)
        result = max(with_house, without_house)
      else:
        result = dp(index + 1, acc, False, memo)

      memo[(index, acc, skip)] = result
      return result
    
    return dp(0, 0, False, {})
S

singhursefamily

· 8 months ago

Educators have a duty to encourage virtue in their students, or at the very least never to encourage vice.

Instead of presenting an example about a thief and unintentionally normalizing robbery, why not substitute an example that will encourage your students to good deeds?

For example, "A benefactor wants to distribute food to families in a neighborhood that recently experienced a natural disaster. In order for the benefactor to remain anonymous he must not drop off food baskets to two consecutive houses. If each house contains the given number of family members, what's the maximum number of people this good man can feed?"