House Robber II: Dynamic Programming with a Twist

The "House Robber II" problem is an extension of the classic House Robber problem, with an added complexity: the houses are arranged in a circle.

Problem Statement

Given a list of non-negative integers representing the amount of money in each house, find the maximum amount of money you can rob tonight without alerting the police. In this version, the first and last houses are adjacent; if you rob one, you cannot rob the other.

Example

• Input: nums = [2, 3, 2] Output: 3 Explanation: Rob the second house (3) because robbing the first and the last house is not allowed due to their adjacency.

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

Dynamic Programming Solution

Breaking Down the Solution

• Base Cases: Handle scenarios with no houses or only one house.
• Rob Houses Linearly: Define a function robLinear that solves the problem for a linear arrangement of houses, using a dynamic programming approach.
• Two Scenarios: Since the houses are in a circle, consider two scenarios - one excluding the first house and the other excluding the last house.
• Maximize the Robbery: Use the robLinear function for both scenarios and return the maximum of the two.

Conclusion

House Robber II introduces an interesting twist to the standard dynamic programming problem by arranging the houses in a circle. This problem requires careful consideration of edge cases and illustrates the adaptability of dynamic programming techniques in solving complex variations of standard problems.

Rust Solution

rob_linear takes houses: &[i32], a borrowed slice, so both &nums[1..] and &nums[..nums.len() - 1] are cheap views into the same Vec<i32> rather than the fresh arrays that JS's nums.slice(...) allocates. The for &amount in houses loop pattern-destructures each &i32 reference back into an i32 by value, so amount is a plain integer in the arithmetic below. Because prev and curr are reassigned each iteration they need let mut, and the running best is computed with the .max method on the integer itself — (prev + amount).max(curr) and case1.max(case2) — instead of a free-standing Math.max.

Go Solution

prev, curr := 0, 0 declares and initialises both accumulators in one parallel short-declaration, and for _, amount := range houses discards the index with the blank identifier _, keeping only the value. Go has no Math.max expression here, so the maximum is spelled out longhand with if prev+amount > curr inside the loop and if case1 > case2 at the end. Slicing nums[1:] and nums[:len(nums)-1] yields views over the same backing array — like Rust's borrows and unlike JS's copying slice — which is safe since robLinear only reads them.