House Robber: A Dynamic Programming Solution

The "House Robber" problem is a fundamental question in dynamic programming. It challenges us to find the maximum amount of money a robber can steal from a row of houses without robbing two adjacent houses, as this would alert the police.

Problem Statement

Given an array of integers representing the amount of money in each house, determine the maximum amount of money you can rob without robbing two adjacent houses.

Example

• Input: nums = [1, 2, 3, 1] Output: 4 Explanation: Rob the first house (1) and the third house (3), totaling 4.

• Input: nums = [2, 7, 9, 3, 1] Output: 12 Explanation: Rob the first house (2), the third house (9), and the fifth house (1), totaling 12.

Dynamic Programming Solution

Breaking Down the Solution

• Base Cases: Handle the cases where there are no houses or only one house.
• Initialize dp Array: Create a dp array to store the maximum amount of money that can be robbed up to each house.
• Dynamic Programming Iteration: Iterate through the array. For each house, calculate the maximum money by either robbing this house and the best house before the previous one, or by not robbing this house and taking the best total from the previous house.
• Return the Maximum Robbery Amount: The last element in the dp array represents the maximum amount of money that can be robbed.

Conclusion

The House Robber problem demonstrates the effectiveness of dynamic programming in solving optimization problems. It shows how to make decisions at each step to maximize the overall outcome while adhering to certain constraints.

Rust Solution

rob takes nums: Vec<i32> by value, so it owns the vector and indexes it freely, and emptiness is checked with the idiomatic nums.is_empty() rather than comparing len() to zero. vec![0i32; n] allocates and zero-fills the dp buffer in a single macro, with the 0i32 literal pinning the element type, and let mut dp makes the mutability explicit. The running maximum uses i32's own .max() method (nums[0].max(nums[1]), then .max(dp[i - 1])) in place of JS's Math.max, and the function ends on the bare tail expression dp[n - 1] — no return, no semicolon.

Go Solution

Go takes the input as an []int slice and uses len(nums) for both the empty and single-element guards, while make([]int, n) allocates the dp slice already zero-filled. With no built-in max used here, each running comparison is spelled out longhand as if/else blocks — once to seed dp[1] and again inside the loop — rather than a single expression like JS's Math.max. n and dp are introduced with the := short declaration, the iteration is the C-style for i := 2; i < n; i++, and the result is return dp[n-1].