Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: House thief

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

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

Reading Progress

0%

Vote for new content