NUHMAN.com

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money hidden, and you cannot rob two adjacent houses because the security system will automatically alert the police if you do. You must determine the maximum amount of money you can rob tonight without alerting the police.

Function Signature:

go

func rob(nums []int) int

Example 1:

go

nums := []int{1, 2, 3, 1}
fmt.Println(rob(nums)) // Output: 4

Example 2:

go

nums := []int{2, 7, 9, 3, 1}
fmt.Println(rob(nums)) // Output: 12

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 400

Approach

The goal is to maximize the total amount of money you can rob, but you can't rob two adjacent houses. The problem can be solved efficiently using Dynamic Programming (DP).

Dynamic Programming Approach:

1. State Definition: Let dp[i] represent the maximum amount of money that can be robbed from the first i houses.
2. Recurrence Relation:

• For each house i, you have two choices:
• Do not rob house i, in which case the maximum money is the same as dp[i-1] (the result from robbing the first i-1 houses).
• Rob house i, in which case you add the value of house i to dp[i-2], because you cannot rob the adjacent house.

1. The recurrence relation is:

lua

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

1. Base Cases:

• dp[0] = nums[0]: If there's only one house, rob it.
• dp[1] = max(nums[0], nums[1]): For two houses, rob the one with the higher value.

1. Space Optimization: Since we only need the last two values (dp[i-1] and dp[i-2]) to compute the current value dp[i], we can reduce the space complexity from O(n) to O(1) by using two variables instead of an entire array.

Time Complexity:

• O(n), where n is the length of the input array nums. We iterate over the array once.

Space Complexity:

• O(1), since we only use two variables to store intermediate results.

Go Implementation

go

package main

import "fmt"

// Function to compute the maximum amount of money you can rob
func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }

    prev2 := 0   // dp[i-2]
    prev1 := nums[0] // dp[i-1]

    for i := 1; i < len(nums); i++ {
        curr := max(prev1, prev2 + nums[i]) // max(dp[i-1], dp[i-2] + nums[i])
        prev2 = prev1 // Update dp[i-2] for the next iteration
        prev1 = curr  // Update dp[i-1] for the next iteration
    }

    return prev1
}

// Helper function to return the maximum of two integers
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    // Test case 1
    nums1 := []int{1, 2, 3, 1}
    fmt.Println(rob(nums1)) // Output: 4

    // Test case 2
    nums2 := []int{2, 7, 9, 3, 1}
    fmt.Println(rob(nums2)) // Output: 12
}

Explanation of the Code:

1. rob function:

• Input: The function takes an array nums representing the amount of money in each house.
• Base Case: If the length of nums is 0, return 0 (no houses to rob). If the length is 1, return nums[0] (only one house to rob).
• Dynamic Programming: We initialize two variables, prev2 and prev1, which represent the maximum money we can rob up to house i-2 and house i-1, respectively.
• For each house i, the maximum amount we can rob is the maximum of:
• Not robbing house i (prev1).
• Robbing house i, in which case we add the value of nums[i] to prev2 (because we can't rob adjacent houses).
• Space Optimization: Only two variables, prev1 and prev2, are used to store the previous results, reducing space complexity to O(1).

2. max function:

• Input: This helper function returns the maximum of two integers a and b.
• Output: It returns the larger of the two values.

3. Main Function:

• The main function contains test cases where the rob function is called with different arrays of house values to check the correctness of the solution.

Example Walkthrough

Example 1:

Input: nums = [1, 2, 3, 1]

1. Base Case: nums has more than 1 element, so we proceed with the DP solution.
2. Initialization:

• prev2 = 0, prev1 = 1 (we rob the first house).

1. Iteration 1 (i = 1): curr = max(1, 0 + 2) = 2, so we update prev2 = 1 and prev1 = 2.
2. Iteration 2 (i = 2): curr = max(2, 1 + 3) = 4, so we update prev2 = 2 and prev1 = 4.
3. Iteration 3 (i = 3): curr = max(4, 2 + 1) = 4, so we update prev2 = 4 and prev1 = 4.
4. Final Output: 4

Example 2:

Input: nums = [2, 7, 9, 3, 1]

1. Base Case: nums has more than 1 element, so we proceed with the DP solution.
2. Initialization:

• prev2 = 0, prev1 = 2 (we rob the first house).

1. Iteration 1 (i = 1): curr = max(2, 0 + 7) = 7, so we update prev2 = 2 and prev1 = 7.
2. Iteration 2 (i = 2): curr = max(7, 2 + 9) = 11, so we update prev2 = 7 and prev1 = 11.
3. Iteration 3 (i = 3): curr = max(11, 7 + 3) = 11, so we update prev2 = 11 and prev1 = 11.
4. Iteration 4 (i = 4): curr = max(11, 11 + 1) = 12, so we update prev2 = 11 and prev1 = 12.
5. Final Output: 12

Conclusion

LeetCode 198: House Robber can be efficiently solved using Dynamic Programming. By using only two variables to track the results of the previous two houses, we achieve O(1) space complexity while maintaining O(n) time complexity.