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

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  function robLinear(houses) {
    let prev = 0,
      curr = 0;
    for (let amount of houses) {
      let temp = curr;
      curr = Math.max(prev + amount, curr);
      prev = temp;
    }
    return curr;
  }

  return Math.max(robLinear(nums.slice(1)), robLinear(nums.slice(0, -1)));
}

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.