Introduction to the House Robber Problem
The House Robber problem is one of the most classic dynamic programming challenges you will encounter in coding interviews and algorithmic problem-solving. It is a perfect entry point for understanding how overlapping subproblems can be solved efficiently using memoization or bottom-up tabulation.
In this tutorial, you will learn what the House Robber problem is, why it matters, how to solve it in Go using multiple approaches, and the best practices you should follow when implementing dynamic programming solutions.
What Is the House Robber Problem?
Imagine you are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, represented by an integer array. However, adjacent houses have security systems connected, and if you rob two adjacent houses on the same night, the alarm will trigger and alert the police.
Given an array of non-negative integers representing the amount of money at each house, your task is to determine the maximum amount of money you can rob tonight without alerting the police.
Example
Consider the input array [2, 7, 9, 3, 1]. The maximum amount you can rob is 12, by robbing houses at index 0 (value 2), index 2 (value 9), and index 4 (value 1). Robbing houses 1 and 3 would only yield 10, which is less.
Why the Problem Matters
The House Robber problem is more than just an interview question. It teaches several fundamental concepts that apply to real-world scenarios:
- Dynamic Programming Foundations: It introduces the idea of breaking a problem into overlapping subproblems and combining their solutions.
- State Transition: It demonstrates how to define a recurrence relation that captures the optimal decision at each step.
- Space Optimization: It shows how a seemingly complex problem can be reduced to constant space usage.
- Real-World Analogues: Similar patterns appear in resource allocation, scheduling, and financial planning problems.
Understanding the Recurrence Relation
The key to solving this problem is recognizing the decision at each house. For every house at index i, you have two choices:
- Rob the house: Add its value to the maximum amount robbed from houses up to index
i - 2. - Skip the house: Carry forward the maximum amount robbed up to index
i - 1.
This gives us the recurrence relation:
dp[i] = max(dp[i-1], dp[i-2] + nums[i])Where dp[i] represents the maximum amount that can be robbed from the first i + 1 houses.
Approach 1: Recursive Solution
The most intuitive approach is a recursive one. At each house, you decide whether to rob it or skip it, then recursively solve the remaining subproblem. While this works, it has exponential time complexity due to repeated calculations.
package main
import "fmt"
func robRecursive(nums []int, i int) int {
if i < 0 {
return 0
}
robCurrent := nums[i] + robRecursive(nums, i-2)
skipCurrent := robRecursive(nums, i-1)
if robCurrent > skipCurrent {
return robCurrent
}
return skipCurrent
}
func rob(nums []int) int {
return robRecursive(nums, len(nums)-1)
}
func main() {
nums := []int{2, 7, 9, 3, 1}
fmt.Println("Maximum amount:", rob(nums))
}This solution is correct but inefficient. For an array of length n, the time complexity is O(2^n), which becomes unusable for even moderately sized inputs.
Approach 2: Top-Down Dynamic Programming with Memoization
To avoid recalculating the same subproblems, we can cache the results of each recursive call. This technique is called memoization and reduces the time complexity to O(n).
package main
import "fmt"
func robMemo(nums []int, i int, memo map[int]int) int {
if i < 0 {
return 0
}
if val, ok := memo[i]; ok {
return val
}
robCurrent := nums[i] + robMemo(nums, i-2, memo)
skipCurrent := robMemo(nums, i-1, memo)
if robCurrent > skipCurrent {
memo[i] = robCurrent
} else {
memo[i] = skipCurrent
}
return memo[i]
}
func rob(nums []int) int {
memo := make(map[int]int)
return robMemo(nums, len(nums)-1, memo)
}
func main() {
nums := []int{2, 7, 9, 3, 1}
fmt.Println("Maximum amount:", rob(nums))
}By storing computed results in a map, each subproblem is solved only once. This is a significant improvement, though the recursive call stack still consumes O(n) space.
Approach 3: Bottom-Up Dynamic Programming with Tabulation
The bottom-up approach eliminates recursion entirely. We build a dp array from left to right, filling each entry based on the recurrence relation. This approach is often preferred in Go because it avoids potential stack overflow issues with deep recursion.
package main
import "fmt"
func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
if n == 1 {
return nums[0]
}
dp := make([]int, n)
dp[0] = nums[0]
if nums[1] > nums[0] {
dp[1] = nums[1]
} else {
dp[1] = nums[0]
}
for i := 2; i < n; i++ {
robCurrent := dp[i-2] + nums[i]
skipCurrent := dp[i-1]
if robCurrent > skipCurrent {
dp[i] = robCurrent
} else {
dp[i] = skipCurrent
}
}
return dp[n-1]
}
func main() {
nums := []int{2, 7, 9, 3, 1}
fmt.Println("Maximum amount:", rob(nums))
}This solution runs in O(n) time and uses O(n) space. It is clear, easy to debug, and performs well for most practical inputs.
Approach 4: Space-Optimized Solution
Looking closely at the recurrence relation, we only ever need the previous two values to compute the current one. This means we can replace the entire dp array with two variables, reducing space complexity to O(1).
package main
import "fmt"
func rob(nums []int) int {
prev2 := 0
prev1 := 0
for _, money := range nums {
current := prev1
if prev2+money > prev1 {
current = prev2 + money
}
prev2 = prev1
prev1 = current
}
return prev1
}
func main() {
nums := []int{2, 7, 9, 3, 1}
fmt.Println("Maximum amount:", rob(nums))
}This is the most efficient solution. It maintains the same O(n) time complexity while using only constant extra space. In production code, this is the version you would typically ship.
Handling Edge Cases
A robust solution must handle edge cases gracefully. Here are the scenarios you should consider:
- Empty array: Return 0, since there are no houses to rob.
- Single house: Return the value of that house.
- Two houses: Return the maximum of the two values.
- All zeros: Return 0, as there is nothing to gain.
The space-optimized solution handles all of these naturally because prev2 and prev1 start at 0, and the loop simply processes each house in sequence.
Testing Your Solution
Writing tests is essential to verify correctness. Go's built-in testing framework makes this straightforward. Below is a test file you can use alongside your implementation.
package main
import "testing"
func TestRob(t *testing.T) {
tests := []struct {
name string
nums []int
expected int
}{
{"empty array", []int{}, 0},
{"single house", []int{5}, 5},
{"two houses", []int{3, 7}, 7},
{"classic example", []int{2, 7, 9, 3, 1}, 12},
{"all same values", []int{4, 4, 4, 4}, 8},
{"increasing values", []int{1, 2, 3, 4, 5}, 9},
{"decreasing values", []int{5, 4, 3, 2, 1}, 9},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
result := rob(tt.nums)
if result != tt.expected {
t.Errorf("rob(%v) = %d, expected %d", tt.nums, result, tt.expected)
}
})
}
}Run the tests using the command go test -v to see detailed output for each case.
Best Practices
When implementing dynamic programming solutions in Go, keep the following best practices in mind:
- Start with the brute force approach: Understanding the recursive solution first helps you identify the recurrence relation before optimizing.
- Identify overlapping subproblems: If the same computation appears multiple times, memoization or tabulation will help.
- Optimize space when possible: Always check whether you can reduce the
dparray to a few variables. - Handle edge cases explicitly: Even if your solution handles them implicitly, adding explicit checks improves readability.
- Write comprehensive tests: Cover empty inputs, single elements, and boundary conditions to ensure robustness.
- Use clear variable names: Names like
prev1andprev2are acceptable, butrobPrevandrobPrevPrevcan be more descriptive in larger solutions.
Extending to the Circular House Robber Variant
A common follow-up question is the circular variant, where the first and last houses are also considered adjacent. To solve this, you run the standard solution twice: once excluding the first house, and once excluding the last house. The answer is the maximum of the two results.
package main
import "fmt"
func robLinear(nums []int) int {
prev2 := 0
prev1 := 0
for _, money := range nums {
current := prev1
if prev2+money > prev1 {
current = prev2 + money
}
prev2 = prev1
prev1 = current
}
return prev1
}
func robCircular(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
if n == 1 {
return nums[0]
}
excludeFirst := robLinear(nums[1:])
excludeLast := robLinear(nums[:n-1])
if excludeFirst > excludeLast {
return excludeFirst
}
return excludeLast
}
func main() {
nums := []int{2, 3, 2}
fmt.Println("Maximum amount (circular):", robCircular(nums))
}This approach elegantly reuses the linear solution and handles the circular constraint by considering two separate scenarios.
Conclusion
The House Robber problem is a fantastic way to build your intuition for dynamic programming. By progressing from a naive recursive solution to a space-optimized one, you learn how to identify recurrence relations, eliminate redundant computations, and reduce memory usage. In Go, the bottom-up and space-optimized approaches are particularly effective because they avoid recursion depth issues and produce clean, idiomatic code. Whether you are preparing for interviews or sharpening your algorithmic skills, mastering this problem gives you a strong foundation for tackling more complex dynamic programming challenges. Practice the variants, write thorough tests, and always look for opportunities to optimize both time and space in your solutions.