The House Robber scenario serves as a well-known illustration of a dynamic programming issue commonly found in algorithmic puzzles and coding interviews. It showcases the process of resolving dilemmas that involve maximizing an outcome while facing restrictions that limit potential decision combinations.
In a basic scenario, the House Robber challenge revolves around a sequence of houses, each holding a specific sum of money. The objective for the thief is to maximize the total amount stolen by strategically robbing houses. Nonetheless, the robber faces a constraint where he cannot target two neighboring houses due to their interconnected security systems. Robbing adjacent houses triggers the alarm system, compromising the thief's heist.
House Robber II (Circular Arrangement)
In House Robber II, a new challenge is introduced where the houses form a circular arrangement. This setup implies that the initial and final houses are next to each other, which complicates the scenario. It's important to note that if the first house is robbed, the last house cannot be robbed, and vice versa.
To address this challenge, the issue can be segmented into two more manageable sub-issues:
- Begin by robbing residences starting from the initial house up to the second-to-last one (excluding the final house).
- Proceed to rob houses from the second residence to the last one (excluding the initial house).
By resolving these two subtasks utilizing the linear dynamic programming technique introduced in House Robber I and subsequently selecting the higher value from the outcomes, we can derive the most efficient solution for the circular layout.
Approach-1: Recursive Approach with Modifications
The method of recursion for tackling the House Robber problem in a sequential layout entails examining every conceivable combination of houses to burglarize, deciding at each instance whether to rob the present house or move on. When dealing with the circular layout in House Robber II, the situation grows more intricate as looting the initial house eliminates the final house and vice versa.
Challenges in Circular Arrangement
Introducing a circular layout creates a connection between the initial and final residences. This signifies:
If you steal from the initial house, you are unable to steal from the final one. If you target the final house, you are unable to target the initial one. To address this issue, we divide the problem into two separate subproblems:
Rob homes starting from the initial house up to the second-to-last house (nums[0] to nums[n-2]).
Rob homes from the second dwelling to the final dwelling (nums[1] to nums[n-1]).
Recursive Solution for Linear Subproblems
We will address these smaller tasks through recursive methods, analyzing two possibilities at each iteration:
- Steal from the current residence and proceed to the dwelling two steps behind.
- Bypass the current residence and transition to the subsequent dwelling.
Program:
#include <iostream>
#include <vector>
#include <algorithm>
// Helper recursive function to calculate the maximum amount of money that can be robbed
int robRecursive(const std::vector<int>& nums, int start, int end) {
// Base case: If the current index is out of range
if (start > end) return 0;
// Recurrence relation: Either skip the current house or rob it
return std::max(robRecursive(nums, start + 1, end), nums[start] + robRecursive(nums, start + 2, end));
}
// Main function to solve the House Robber II problem
int rob(std::vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return std::max(nums[0], nums[1]);
// Case 1: Rob houses from the first house to the second-to-last house
int case1 = robRecursive(nums, 0, n - 2);
// Case 2: Rob houses from the second house to the last house
int case2 = robRecursive(nums, 1, n - 1);
// Return the maximum amount from both cases
return std::max(case1, case2);
}
int main() {
std::vector<int> nums = {2, 3, 2};
std::cout << "Maximum amount that can be robbed: " << rob(nums) << std::endl;
return 0;
}
Output:
Maximum amount that can be robbed: 3
Explanation:
The presented solution employs a recursive strategy with adjustments to address the circular layout of houses in the House Robber II dilemma. By dividing the issue into two separate linear subtasks and resolving them recursively, the solution guarantees the maximum possible robbery amount while adhering to the restriction of avoiding robbing neighboring houses.
Even though this iterative method is clear and showcases the problem-solving strategy, it may not be efficient when dealing with significant input sizes because of its exponential time complexity. In real-world scenarios, dynamic programming techniques are favored to enhance efficiency and minimize repetitive computations.
Base Case
The auxiliary function robRecursive manages the scenario when the present index falls outside the acceptable range. In cases where the initial index surpasses the final index (start > end), a return value of 0 is triggered. This signifies that there are no more residences to factor in within this particular sub-issue.
Recurrence Relation
The fundamental concept behind recursion is to examine two options for every residence:
Proceed to the Next Property: Transition to the subsequent property involves invoking the robRecursive(nums, start + 1, end) function.
Plunder the Present Residence: Combine the funds from the current dwelling with the proceeds from looting the subsequent house. This can be accomplished by invoking robRecursive(nums, start + 2, end) and then including nums[start] in the total.
When evaluating each household, the function computes the optimal outcome by determining the maximum value between the two available options. This approach guarantees thorough examination of all potential house combinations, maintaining the key restriction of avoiding theft from consecutive houses.
Main Function Logic
The rob function serves as the primary function responsible for managing the circular layout of residences. Here is the logic broken down into sequential steps:
In a scenario where only a single house is present, the function will promptly return the value of that house as there are no neighboring houses to take into account.
In a scenario with two houses, the function will output the highest value among them, as there are no constraints against robbing either house due to adjacency concerns.
When dealing with more than two houses, the issue is split into two subproblems to address the cyclic arrangement effectively:
Case 1: Steal from residences starting from the initial house up to the penultimate one, excluding the final house to prevent issues with circular adjacency.
Rob houses starting from the second one up to the final house, excluding the initial house to prevent circular adjacency issues.
The function leverages the robRecursive helper function to address the subproblems before comparing and selecting the maximum outcome between the two scenarios. By following this method, the solution maintains adherence to the circular adjacency constraint and successfully determines the highest achievable robbery amount.
Complexity Analysis:
Time Complexity
The time complexity of the recursive method can increase significantly because of the inherent characteristics of recursion without memoization. Now, let's break it down and examine it systematically:
Recursive Function Calls:
In the robRecursive function, each invocation at a specific index triggers two additional recursive calls: one to bypass the current dwelling (robRecursive(nums, start + 1, end)) and another to steal from the current dwelling (robRecursive(nums, start + 2, end)).
This branching pattern leads to a growing number of function calls. More precisely, each invocation divides into two, forming a binary tree structure of calls.
Exponential Growth:
At every residence, the function initiates two recursive invocations, resulting in a maximum of 2n function calls under unfavorable circumstances, with n representing the quantity of residences.
This outcome stems from the potential depth of the recursive call tree reaching up to n (assuming each call simply bypasses the current house), with each subsequent level potentially doubling the number of calls compared to the previous level.
Overall Time Complexity:
Because of the rapid increase in recursive calls, the time complexity of the robRecursive function amounts to O(2n).
As a result, due to the fact that the primary function rob invokes this recursive function twice (once for each subtask), the total time complexity stays at O(2n). This is due to the omission of constant factors in Big-O notation.
Space Complexity
The space efficiency of the recursive method depends on the memory allocated for the function call stack and any extra space required by the function implementation.
Function Call Stack:
Each iteration of the recursive function contributes an additional frame to the call stack until it reaches the base case.
The highest limit of the call stack correlates with the extent of the recursion chain, reaching a maximum of n when each recursive step skips just one house.
Space Usage Per Call:
Each function call requires a fixed quantity of memory (disregarding the recursive function calls), mainly for holding the arguments and the memory address for returning.
Therefore, the space complexity per call is O(1).
Overall Space Complexity:
The amount of space needed for the call stack could potentially reach O(n) in the most unfavorable scenario, with n denoting the quantity of houses. This occurs when each call simply bypasses the current house and proceeds to the subsequent one, resulting in a cascade of recursive calls as extensive as the total number of houses.
Therefore, the total space complexity of the recursive approach amounts to O(n).
Appoach-2: Memoization (Top-Down Dynamic Programming)
In the context of the House Robber II challenge, the dwellings are positioned in a circular layout, implying that the initial and final houses are next to each other. The objective is to calculate the highest possible sum of money that can be stolen without setting off any alarms, specifically by avoiding robbing two neighboring houses.
To address the circular layout, we split the issue into two sequential subtasks:
- Stealing from residences starting from the initial one up to the second-to-last one.
- Stealing from residences starting from the second one up to the final one.
This guarantees that the first and last houses are not included in the same subproblem, effectively preventing any adjacency problems.
Program:
#include <iostream>
#include <vector>
#include <algorithm>
// Helper function to perform memoized recursion
int robMemo(const std::vector<int>& nums, int start, int end, std::vector<int>& memo) {
if (start > end) return 0;
if (memo[start] >= 0) return memo[start];
memo[start] = std::max(robMemo(nums, start + 1, end, memo), nums[start] + robMemo(nums, start + 2, end, memo));
return memo[start];
}
// Main function to solve the House Robber II problem
int rob(std::vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return std::max(nums[0], nums[1]);
// Case 1: Rob houses from the first house to the second-to-last house
std::vector<int> memo1(n, -1);
int case1 = robMemo(nums, 0, n - 2, memo1);
// Case 2: Rob houses from the second house to the last house
std::vector<int> memo2(n, -1);
int case2 = robMemo(nums, 1, n - 1, memo2);
// Return the maximum amount from both cases
return std::max(case1, case2);
}
int main() {
std::vector<int> nums = {2, 3, 2};
std::cout << "Maximum amount that can be robbed: " << rob(nums) << std::endl;
return 0;
}
Output:
Maximum amount that can be robbed: 3
Explanation:
Recursive Function with Memoization (robMemo):
This function executes the recursive calculation to find the highest possible amount of money that can be stolen from a defined range of houses.
Base Scenario: When the initial index surpasses the final index, it indicates that there are no more properties to assess, prompting the method to output a value of 0.
Memoization Verification: Prior to executing any calculations, the function verifies whether the outcome for the existing starting index has been previously calculated and preserved in the memo array. If so, the function retrieves this preserved result to prevent unnecessary recalculations.
If the outcome is not stored in the memo array, the function computes the highest possible sum that can be stolen by either individual:
Skipping the present residence and moving on to the subsequent residence (start + 1).
Stealing from the present household while also planning for the one following the subsequent one (start + 2).
The function proceeds to save the higher value among these two in the memo array and then proceeds to return it.
Main Function (rob):
In the scenario where only one house exists, the function will directly return its value as there are no neighboring houses to take into account.
In the scenario with two houses, the function will output the highest value achievable by robbing either of them, as there are no constraints regarding adjacency.
Complexity Analysis:
Time Complexity
The time complexity of the memoization technique is mainly influenced by the recursive function robMemo, which computes the maximum possible stolen amount from a sequence of houses through dynamic programming.
Recursive Calls:
The robMemo function is executed repeatedly for every dwelling within the specified range.
For every individual dwelling, the function initiates two invocations: one for the subsequent dwelling and another for the dwelling following it. Nonetheless, as a result of memoization, the outcome for each dwelling is calculated just once and then preserved in the memo array.
Memoization:
After calculating a result for a specific starting point, it gets saved in the memo array. Any future requests for the same starting point will promptly retrieve the stored result.
This decreases the amount of calculations to a single traversal of the houses.
Two Subproblems:
The issue is segmented into two subtasks: stealing from the initial house to the second-to-last house and looting from the second house to the final house.
Each subtask requires a linear amount of calculations thanks to the memoization technique in place.
Considering the aforementioned factors, the time complexity for addressing each subtask is O(n), with 'n' representing the quantity of houses. As two subtasks are resolved, the total time complexity persists as: O(n).
Space Complexity
The space complexity is defined by the memory allocated for memoization and the stack space required for recursion.
Memoization Array:
For every individual subtask, an array of size n is utilized for memoization to store interim outcomes. This particular array guarantees that the outcome for each residence is calculated just once.
We require two memoization arrays, each dedicated to a specific subproblem.
Recursion Call Stack:
In the event of a worst-case scenario, the recursion depth has the potential to extend up to n. Nevertheless, with the implementation of memoization, every recursion level will access the cached outcomes, thereby reducing the frequency of recursive invocations.
Combined Space Usage:
Each cache array adds O(n) space complexity. The recursive function call stack also contributes O(n) space. As both the memoization arrays and the recursion stack grow proportionally with the number of houses, the total space complexity is O(n).
Approach-3: Space-Optimized Dynamic Programming
The memory-efficient dynamic programming technique for addressing the House Robber II issue capitalizes on the insight that monitoring just the previous two states is adequate for calculating the current state. This results in a notable decrease in space complexity, shifting it from O(n) to O(1).
Two Variables Instead of a DP Array:
In the conventional dynamic programming method, we manage an array called dp where dp[i] signifies the highest sum of money that can be stolen from the initial house up to the i-th house.
In the memory-efficient method, two variables, prev1 and prev2, are employed to denote the previous two calculated states:
prev1 represents the highest sum stolen from the house before the current one (i.e., dp[i-1]).
The term prev2 represents the highest sum of money stolen before the house preceding the one currently being considered (i.e., dp[i-2]).
Program:
#include <iostream>
#include <vector>
#include <algorithm>
int robLinear(const std::vector<int>& nums, int start, int end) {
if (start == end) return nums[start];
int prev1 = 0, prev2 = 0;
for (int i = start; i <= end; ++i) {
int temp = prev1;
prev1 = std::max(prev1, nums[i] + prev2);
prev2 = temp;
}
return prev1;
}
int rob(std::vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return std::max(nums[0], nums[1]);
int case1 = robLinear(nums, 0, n - 2);
int case2 = robLinear(nums, 1, n - 1);
return std::max(case1, case2);
}
int main() {
std::vector<int> nums = {2, 3, 2};
std::cout << "Maximum amount that can be robbed: " << rob(nums) << std::endl;
std::vector<int> nums2 = {1, 2, 3, 1};
std::cout << "Maximum amount that can be robbed: " << rob(nums2) << std::endl;
return 0;
}
Output:
Maximum amount that can be robbed: 3
Maximum amount that can be robbed: 4
Explanation:
Helper Function: robLinear
The robLinear function is created to address the linear variation of the house burglary issue within a defined range of houses, starting from the beginning to the end.
Parameters:
const std::vector<int>& nums: The collection holding the values associated with the residences.
The initial index indicates the beginning of the range of houses to be taken into account.
The termination point: Represents the concluding index within the specified range of houses for evaluation.
Base Case:
If the specified range contains only a single house (where the start value is equal to the end value), the function will simply return the value of that particular house since there are no additional houses within the range to take into account.
Variables:
The variable prev1 is utilized to monitor the highest sum of money that can be stolen up to the house preceding the current one.
prev2 stores the highest sum of money that can be stolen from houses leading up to the one just before the current house.
Iterative Computation:
The function loops through the houses starting from the beginning to the end. For each house, it calculates the highest possible sum that can be stolen by evaluating two scenarios:
Avoiding burglarizing the present residence: This implies that the highest value is equivalent to the prev1 value.
Stealing from the present residence involves taking the highest possible sum, which comprises the value of the current dwelling (nums[i]) plus prev2. The function subsequently adjusts prev1 to reflect the greater value between these two scenarios.
Before making changes to prev1, the existing value of prev1 is saved in a temporary variable called temp. This allows for updating prev2 to the previous value that was stored in prev1.
Once the iteration finishes, the variable prev1 stores the highest count of houses that can be burglarized within the designated range.
Main Function: rob
The rob function leverages the robLinear helper function to manage the circular layout of houses.
Edge Cases:
If the array contains only a single house, the function will output the value of that specific house because there are no neighboring houses to take into account.
If there are two residences, the function will output the larger of the two values, as we are restricted to robbing only one to prevent problems with neighboring thefts.
Breaking the Problem into Two Subproblems:
To address the circular configuration, the function divides the issue into two separate linear subtasks:
Case 1: When planning to burglarize residences, it is advisable to target properties starting from the initial house up to the penultimate one (nums[0] to nums[n-2]). This strategy ensures that the final house is not part of the plan.
Consider targeting houses for burglary starting from the second house up to the last house in the sequence (nums[1] to nums[n-1]). By doing this, the first house is intentionally excluded from the list of potential targets.
Using robLinear to Solve Subproblems:
For Case 1, the function invokes robLinear using the range from 0 to n-2.
For Case 2, the robLinear function is invoked with the range starting from 1 up to n-1.
Returning the Final Result:
The function calculates the higher value obtained from the outcomes of the two subtasks (case1 and case2), while also maintaining the condition of not burglarizing both the initial and final residences.
Complexity Analysis:
Time Complexity
The time complexity of the robLinear function is O(n) because it iterates through each house within the designated range only once.
As the rob function invokes robLinear twice, once for each subproblem, the total time complexity stays at O(n).
Space Complexity
The space complexity of the robLinear function is O(1) as it solely requires a fixed amount of additional space (prev1, prev2, and temp).
The total space complexity of the rob function remains O(1) as the auxiliary function does not necessitate extra space relative to the input size.
