Published on

# House Robber Problem

Authors

## Problem

You are planning to rob houses on a specific street, and you know that every house on the street has a certain amount of money hidden. The only thing stopping you from robbing all of them in one night is that adjacent houses on the street have a connected security system. The system will automatically trigger an alarm if two adjacent houses are broken into on the same night.

Given a list of non-negative integers nums representing the amount of money hidden in each house, determine the maximum amount of money you can rob in one night without triggering an alarm.

Example

For nums = [1, 1, 1], the output should be
solution(nums) = 2.

The optimal way to get the most money in one night is to rob the first and the third houses for a total of 2.

## Solution

Robbing houses may be illegal, but solving the problem of finding the maximum amount of money that can be robbed without triggering an alarm can be a fun programming exercise. In this blog post, we will use Go to solve this problem by implementing a dynamic programming solution.

First, let's understand the problem statement. We have a list of non-negative integers representing the amount of money hidden in each house on a street. We cannot rob adjacent houses on the same night as they have a connected security system that will trigger an alarm. We need to find the maximum amount of money we can rob in one night without triggering an alarm.

To solve this problem using dynamic programming, we will create an array called dp of the same length as nums. dp[i] will represent the maximum amount of money that can be robbed up to house i without triggering an alarm. We will use the following recurrence relation to fill the dp array:

_1dp[i] = max(dp[i-1], dp[i-2]+nums[i])

The above relation states that we have two choices for robbing the $i^{th}$ house. Either we can rob it and add its value to the maximum amount of money we can rob up to the $(i-2)^{th}$ house, or we can skip the $i^{th}$ house and consider the maximum amount of money we can rob up to the $(i-1)^{th}$ house.

Let's implement the solution in Go:

_48package main_48_48import (_48 "testing"_48)_48_48func solution(nums []int) int {_48 if len(nums) == 0 {_48 return 0_48 }_48_48 if len(nums) == 1 {_48 return nums[0]_48 }_48_48 dp := make([]int, len(nums))_48 dp[0] = nums[0]_48 dp[1] = max(nums[0], nums[1])_48_48 for i := 2; i < len(nums); i++ {_48 dp[i] = max(dp[i-1], dp[i-2]+nums[i])_48 }_48_48 return dp[len(nums)-1]_48}_48_48func max(a, b int) int {_48 if a < b {_48 return b_48 }_48_48 return a_48}_48_48func TestLastIndex(t *testing.T) {_48 tests := []struct {_48 list []int_48 want int_48 }{_48 {list: []int{1, 1, 2, 1}, want: 3},_48 {list: []int{1, 1, 1}, want: 2},_48 }_48 for _, tt := range tests {_48 if got := solution(tt.list); got != tt.want {_48 t.Errorf("LastIndex(%v) = %v, want %v", tt.list, got, tt.want)_48 }_48 }_48}

## Time Complexity

The time complexity of the solution is $O(n)$, where n is the length of the input array. We only need to iterate over the input array once to fill the dp array using the recurrence relation. The time complexity of the max function we used is constant, so it does not affect the overall time complexity of the solution.

## Space Complexity

The space complexity of the solution is $O(n)$. We created a dp array of the same length as the input array, which requires $O(n)$ space. We did not use any extra data structures, so the space complexity of our solution is optimal.

In conclusion, our solution has a time complexity of $O(n)$ and a space complexity of $O(n)$, which is efficient and optimal.