House Robber 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.

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:

dp[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:

package main

import (
	"testing"
)

func solution(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	if len(nums) == 1 {
		return nums[0]
	}

	dp := make([]int, len(nums))
	dp[0] = nums[0]
	dp[1] = max(nums[0], nums[1])

	for i := 2; i < len(nums); i++ {
		dp[i] = max(dp[i-1], dp[i-2]+nums[i])
	}

	return dp[len(nums)-1]
}

func max(a, b int) int {
	if a < b {
		return b
	}

	return a
}

func TestLastIndex(t *testing.T) {
	tests := []struct {
		list []int
		want int
	}{
		{list: []int{1, 1, 2, 1}, want: 3},
		{list: []int{1, 1, 1}, want: 2},
	}
	for _, tt := range tests {
		if got := solution(tt.list); got != tt.want {
			t.Errorf("LastIndex(%v) = %v, want %v", tt.list, got, tt.want)
		}
	}
}

Try it your self with adding other test case at https://go.dev/play/p/Od3Q5JB4Bhl

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.

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.