Dynamic Programming Simplified - Part 2

Problem statement



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.

Goal: Calculate the maximum money you can rob without robbing two adjacent houses.

Problem breakdown

Unlike Fibonacci, this problem's recursive pattern isn't immediately obvious. We'll use the same technique: start with the simplest cases.

Base cases:

0 houses: Maximum = 0
1 house (m₁): Maximum = m₁ (rob the only house)
2 houses (m₁, m₂): Maximum = max(m₁, m₂) (rob the better house)

Building the pattern:

3 houses: f(3) = max(m₁ + m₃, m₂)

Either rob houses 1 and 3, or just house 2
4 houses: f(4) = max(m₄ + f(2), f(3))

Either rob house 4 plus optimal solution for first 2 houses, or optimal solution for first 3 houses
5 houses: f(5) = max(m₅ + f(3), f(4))

General pattern: f(n) = max(nums[n] + f(n-2), f(n-1))

When adding a new house, you have two choices: 1. Rob it: Get its money + optimal solution excluding the previous house 2. Skip it: Keep the optimal solution including the previous house

Take whichever gives more money.

Scala Implementation

Let's implement this using pure functional tail recursive style:

// file: house-robber.sc
def rob(houses: Array[Int]): Int =
  def go(i: Int, prevMax: Int, currMax: Int): Int =
    if i >= houses.length then currMax
    else
      val newMax = math.max(houses(i) + prevMax, currMax)
      go(i + 1, currMax, newMax)
  
  if houses.isEmpty then 0
  else go(0, 0, 0)

// Test cases
val houses1 = Array(2, 7, 9, 3, 1)
val houses2 = Array(2, 1, 1, 2)
val houses3 = Array(5)

println(rob(houses1)) // output: 12 (rob houses with 2, 9, 1)
println(rob(houses2)) // output: 4 (rob houses with 2, 2)
println(rob(houses3)) // output: 5 (rob the only house)

How it works:

prevMax: Maximum money robbed up to house i-2
currMax: Maximum money robbed up to house i-1
At each house, we calculate: max(house[i] + prevMax, currMax)
This gives us the optimal choice: rob current house + best from i-2, or skip current house

The time complexity is O(n) and space complexity is O(1)