House Robber

1. Problem Description

You are a professional robber planning to rob houses along a street. Each house contains some cash. The only constraint is that adjacent houses have connected security systems, and the alarm will automatically trigger if two adjacent houses are broken into on the same night.

Given a non-negative integer array representing the amount of money in each house, calculate the maximum amount you can rob in one night without triggering the alarm.

2. Approach

1. Approach 1
   • Accumulate odd/even positions while carrying forward the best result
2. Approach 2
   • DFS + memoization
   • Rob the current house or skip it, then take the larger result

3. Implementation

3.1. Odd/Even Sums with Best Result Carried Forward

//2 1 1 2
func rob(nums []int) int {
	sumOdd := 0
	sumEven := 0

	for i := 0; i < len(nums); i++ {
		if i%2 == 0 {
			sumEven += nums[i]
			sumEven = Max(sumOdd, sumEven)
		} else
		{
			sumOdd += nums[i]
			sumOdd = Max(sumOdd, sumEven)
		}
	}

	return Max(sumOdd, sumEven)
}

3.2. DFS + Memoization

func rob(nums []int) int {
    memo := make(map[int]int, 0)
    return robDFS(nums, 0, memo)
}

func robDFS(nums []int, index int, memo map[int]int) int {
    count, ok := memo[index]
    if ok {
        return count
    }
    if index >= len(nums) {
        return 0
    }

    // Rob the current house
    leftCount := nums[index] + robDFS(nums, index+2, memo)
    // Skip the current house
    rightCount := robDFS(nums, index+1, memo)
    // Take the larger result
    count = max(leftCount, rightCount)
    memo[index] = count
    return count
}

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

4. References

• If You Don’t Know Dynamic Programming, Start Here: Memoized Recursion - House Robber - LeetCode