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

· 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, {})