House Robber

class Solution {
public:
    int rob(vector<int>& arr) {
        int len = arr.size();

        // Edge case for empty array.
        if (len == 0) {
            return 0;
        }

        int next, nextPlusOne;

        // Initialize for the base case.
        nextPlusOne = 0;
        next = arr[len - 1];

        // Implement the iterative DP logic.
        for (int j = len - 2; j >= 0; --j) {
            // Find the maximum possible robbery amount.
            int maxRob = max(next, nextPlusOne + arr[j]);

            // Shift values for the next iteration.
            nextPlusOne = next;
            next = maxRob;
        }

        return next;
    }
};

The provided C++ solution addresses the "House Robber" problem, where you must determine the maximum amount of money that can be robbed without triggering an alarm. This situation simulates a linear array of houses, where each house contains a certain amount of money, but adjacent houses cannot be robbed consecutively.

The solution adopts a dynamic programming approach to solve the problem efficiently. Below provides a step-by-step break down of the code functionality:

• Initialize a check for an empty array of houses. If the array is empty, return zero since there's nothing to rob.

• Setup initial variables next and nextPlusOne to store the prospective robbery amounts. These variables help in storing the results of sub-problems for iterative calculation.

• Start from the second-to-last house and decide at each house (moving backwards) whether to rob it or skip it. This decision is based on comparing the potential robbery amount from the current house plus the amount stored in nextPlusOne, against the amount in next (which represents not robbing the current house).

• Update nextPlusOne and next through each iteration to carry forward the maximum robbery amounts calculated.

• Finally, the amount in next after the loop ends represents the maximum money that can be robbed.

This method is efficient and avoids recalculating amounts for each sub-array of houses, thus significantly reducing computation time compared to a naive recursive approach.

class Solution {
    public int steal(int[] homes) {
        int count = homes.length;

        if (count == 0) {
            return 0;
        }

        int nextHouse, nextPlusOneHouse;

        nextPlusOneHouse = 0;
        nextHouse = homes[count - 1];

        for (int i = count - 2; i >= 0; i--) {
            int maxSteal = Math.max(nextHouse, nextPlusOneHouse + homes[i]);

            nextPlusOneHouse = nextHouse;
            nextHouse = maxSteal;
        }

        return nextHouse;
    }
}

The given Java program solves the "House Robber" problem where you must determine the maximum amount of money you can steal without robbing two adjacent houses. Here's how the solution works:

• Store the number of houses in the variable count.
• If count equals zero, return 0 because there are no houses to rob.
• Initialize two variables, nextHouse and nextPlusOneHouse. These will be used to keep track of the maximum profits from the current house to the end, and from the house after the next to the end, respectively.
• Set nextPlusOneHouse to 0 and nextHouse to the value of the last house.
• Utilize a loop to iterate through the houses from second-to-last to the first. For each house, calculate the maximum value that can be stolen up to that house by comparing:
  • Stealing from the current house plus the nextPlusOneHouse value.
  • Not stealing from the current house and taking the nextHouse value instead.
• Update nextPlusOneHouse and nextHouse accordingly to reflect the choices made.
• When the loop concludes, nextHouse contains the maximum amount of money that can be stolen without triggering the security systems.

This solution employs dynamic programming principles to efficiently solve the problem with a time complexity of O(n) and space complexity O(1), making it optimal for large input sizes.

class Solution:

    def steal(self, houses: List[int]) -> int:

        if not houses:
            return 0

        count_houses = len(houses)

        next_plus_one = 0
        next_house = houses[count_houses - 1]

        for j in range(count_houses - 2, -1, -1):
            max_profit = max(next_house, next_plus_one + houses[j])
            next_plus_one = next_house
            next_house = max_profit

        return next_house

This Python solution addresses the "House Robber" problem. The function steal takes an array houses as input, where each element represents the amount of money in each house. The objective is to return the maximum amount of money you can rob without robbing two adjacent houses.

• Start by checking if the houses array is empty. If it is, return 0 since there's nothing to rob.
• Determine the number of houses using len(houses).
• Initialize two variables, next_plus_one and next_house. next_plus_one keeps track of the maximum profit from houses beyond the next one, and next_house keeps a record of the profit considering the current house as the starting point.
• Iterate backward through the houses list starting from the second last item to the first.
• For each house, calculate the maximum profit by comparing the profit of skipping the current house (next_plus_one plus the current house's money) with the profit of robbing the next house (next_house).
• Update next_plus_one and next_house for the next iteration.
• Finally, return the value of next_house, which holds the maximum profit achievable based on the provided input.

This approach uses dynamic programming principles, specifically a bottom-up method, to ensure an optimal solution. By iterating from the end towards the beginning of the list, it efficiently determines the maximum amount of money that can be robbed under the given constraints.