House Robber II

class Solution {
public:
    int houseRobber(vector<int>& houses) {
        if (houses.size() == 0) return 0;

        if (houses.size() == 1) return houses[0];

        int rob1 = robRange(houses, 0, houses.size() - 2);
        int rob2 = robRange(houses, 1, houses.size() - 1);

        return max(rob1, rob2);
    }

private:
    int robRange(vector<int>& houses, int start, int end) {
        int prev = 0, curr = 0;
        for (int i = start; i <= end; ++i) {
            int temp = curr;
            curr = max(houses[i] + prev, curr);
            prev = temp;
        }

        return curr;
    }
};

This solution addresses the "House Robber II" problem, which extends the basic house robber problem by dealing with houses arranged in a circle, meaning the first and last house are adjacent. The approach implemented in C++ involves dynamic programming, where the main challenge is to avoid the circular condition (first house is adjacent to the last).

Given a class Solution with two primary functions:

• houseRobber(vector<int>& houses): Determines the maximum amount of money that can be robbed. Handles special cases where the number of houses is zero (returns 0) or one (returns the value of the only house). The function solves the problem by considering two scenarios:

  1. Robbing houses from the first to the second-last (ignoring the last house due to circular arrangement).
  2. Robbing houses from the second to the last (ignoring the first house).

  It then returns the maximum of the two scenarios using the helper function robRange.

• robRange(vector<int>& houses, int start, int end): A helper function that implements the dynamic programming part of the solution for a specified range of houses. It iterates through the houses, deciding at each step whether to rob the current house or skip it based on the maximum robberies calculated from previous houses.

This function uses two variables, prev and curr, to store the maximum robbery amounts up to the previous house and the current house, respectively, thereby avoiding the use of extra memory for dp array.

The approach in this solution efficiently handles the circular house arrangement by breaking it down into two linear subproblems and is optimal with a time complexity of O(n), where n is the number of houses. The use of iterative dynamic programming with constant space makes it space-efficient as well.

class Solution {
    public int robHouses(int[] houses) {
        if (houses.length == 0) return 0;
        if (houses.length == 1) return houses[0];

        int maxOption1 = computeMax(houses, 0, houses.length - 2);
        int maxOption2 = computeMax(houses, 1, houses.length - 1);

        return Math.max(maxOption1, maxOption2);
    }

    public int computeMax(int[] houses, int start, int finish) {
        int prevMax = 0;
        int beforePrevMax = 0;

        for (int i = start; i <= finish; i++) {
            int currentHouse = houses[i];
            int temp = prevMax;

            prevMax = Math.max(beforePrevMax + currentHouse, prevMax);
            beforePrevMax = temp;
        }

        return prevMax;
    }
}

The provided Java code addresses the problem of robbing houses arranged in a circle, ensuring that the robber does not rob two adjacent houses or the first and last house together, which are considered adjacent due to the circular arrangement. This is a variation of the House Robber problem where the houses are placed in a straight line.

• The robHouses method first checks if there are no houses or only one house. If there are no houses, it returns 0 as there's nothing to rob. If there's only one house, it returns the value of that house since there's no adjacency issue with a single house.
• The method then calculates the maximum amount that can be robbed in two scenarios:
  • Ignoring the last house (computeMax from the first house to the second-to-last house).
  • Ignoring the first house (computeMax from the second house to the last house).
• It uses a helper method, computeMax, to compute the maximum money that can be robbed for a given range of houses. This method uses dynamic programming where prevMax stores the maximum robbed amount considering the house before the current one, and beforePrevMax stores the maximum amount considering two houses before the current one.
• For each house in the specified range (start to finish), the maximum robbed amount up to that house is updated. The expression Math.max(beforePrevMax + currentHouse, prevMax) ensures that the program does not select two adjacent houses.
• The final result returned by robHouses is the maximum value obtained between the two computed scenarios using Math.max(maxOption1, maxOption2).

This approach ensures optimal use of resources, leveraging the characteristics of dynamic programming to efficiently solve the problem without violating the neighborhood constraints set by the problem statement.

class Solution:
    def rob_homes(self, houses: List[int]) -> int:
        if not houses or len(houses) == 0:
            return 0

        if len(houses) == 1:
            return houses[0]

        return max(self.simple_rob(houses[:-1]), self.simple_rob(houses[1:]))

    def simple_rob(self, houses: List[int]) -> int:
        last = 0
        last_but_one = 0
        for amount in houses:
            current = last
            last = max(amount + last_but_one, last)
            last_but_one = current
        return last

This summary outlines a Python solution for the problem where you aim to determine the maximum amount of money that can be robbed from a row of houses, considering the first and last houses are adjacent (forming a circle). The provided Python class, named Solution, includes methods that implement a dynamic programming approach to solve the problem effectively.

In the rob_homes method:

• Initially, handle edge cases where the list of houses is empty or contains only one house.
• If there's only one house, return the value of that house.
• For multiple houses, the problem is broken down into two scenarios due to the circular arrangement:
  • Robbing the houses from the start to the second-to-last.
  • Robbing the houses from the second house to the last.

The choice between these two scenarios is determined by which offers a greater total return, obtained using the max function.

The simple_rob method, used in both scenarios, employs the dynamic programming technique for a linear sequence of houses:

• Initialize two trackers, last and last_but_one, to manage the maximum amounts that can be robbed up to the current house without triggering alarms.
• Loop through each amount in the list of houses. At each step, compute the maximum money that can be robbed either by including the current house or skipping it.
• Update the trackers accordingly.

In essence, with this solution, you effectively account for the circular arrangement by considering both linear sub-problems, ensuring optimal theft strategy without alerting the house security systems.