< Back




198. House Robber

Dynamic programming problem that was a little tougher than expected. So we're asked to maximize
across the list, nums, the sum of elements that are not adjacent to each other. In order to solve
this iteratively, which is the coolest solution, we need to think about the solution recursively.

Think of nums as a graph, and starting from nums[0] we can choose to rob the current house (node)
or not. If we rob the current house, we can't rob nums[1], we have to rob nums[2]. If don't rob the
current house, we can rob nums[1]. So we can see that the solution is the maximum of the two choices
at each step.

In a recursive dynamic programming solution, we would store this answer in a dictionary to memoize
the result. That way, during other recursive calls, we don't have to recalculate the sum for a node.

Solving this iteratively, we store our sums in a table, allowing us to do an O(1) lookup for a
particular choice. Just like we described earlier, each day we have two choices: rob the current
house or don't rob the current house. We store the maximum sum for each choice in the table, and
return the maximum sum at the end of the iteration.

The solution is as follows:


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

          n = len(nums)
          arr = [0] * (n + 1)
          arr[n], arr[n - 1] = 0, nums[n - 1]

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

          return arr[0]


_ Time Complexity:

  O(n) - Where n is the length of the nums list.

_ Space Complexity:

  O(n) - We store the sums in a table of size n + 1.