grid47 Exploring patterns and algorithms
Oct 16, 2024
6 min read
Solution to LeetCode 213: House Robber II Problem
You are tasked with designing a strategy to rob houses along a circular street, where no two adjacent houses can be robbed on the same night. The goal is to maximize the total money stolen without triggering security alarms.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers representing the amount of money at each house along the street. The houses are arranged in a circle.
Example: [3, 5, 1, 6]
Constraints:
• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000
Output: The output should be the maximum amount of money that can be robbed without robbing two adjacent houses.
Example: For input [3, 5, 1, 6], the output is 9.
Constraints:
Goal: Design an efficient algorithm that calculates the maximum amount of money that can be stolen, taking into account the circular arrangement of houses.
Steps:
• Use dynamic programming to solve the problem. Consider two cases: one where the first house is included and one where it is not.
• For each case, use dynamic programming to calculate the maximum money that can be robbed while ensuring adjacent houses are not robbed.
Goal: The solution should efficiently handle up to 100 houses, each with a potential value between 0 and 1000.
Steps:
• The input size will be manageable (1 <= nums.length <= 100).
• The maximum value of each house's money is 1000.
Assumptions:
• The houses are in a circular arrangement.
• Adjacent houses cannot be robbed together.
• Input: Example 1
• Explanation: In this example, you can rob houses 1 and 3 to maximize the stolen amount, totaling 9.
• Input: Example 2
• Explanation: For this input, robbing houses 1, 3, and 5 gives a total of 12, which is the maximum amount.
Approach: We use dynamic programming to solve this problem, considering two possible cases: one where the first house is robbed and one where it is not. We then apply a standard dynamic programming approach to each case.
Observations:
• Dynamic programming is a natural fit because we need to decide at each step whether to rob a house or skip it, based on the previous decisions.
• We will break the problem into two smaller subproblems: one where we exclude the first house and one where we include the first house.
Steps:
• Define a helper function for dynamic programming to calculate the maximum money robbed, considering the first house as part of the sequence.
• Repeat the calculation excluding the first house and take the maximum of both results.
Empty Inputs:
• If the input is an empty array, the result should be 0.
Large Inputs:
• The solution should efficiently handle cases where the number of houses is large (up to 100).
Special Values:
• If all houses contain 0 money, the maximum amount that can be robbed is 0.
Constraints:
• Handle edge cases such as arrays with only one house, or with houses containing no money.
introb(vector<int>& nums) {
int n = nums.size();
if(n ==1) return nums[0];
vector<int> dp(n, 0);
dp[0] =0;
dp[1] = nums[0];
for(int i =2; i < n; i++)
dp[i] = max(dp[i -1], dp[i -2] + nums[i -1]);
int r1 = dp[n -1];
dp.resize(n +1, 0);
dp[1] =0;
dp[2] = nums[1];
for(int i =3; i < n +1; i++)
dp[i] = max(dp[i -1], dp[i -2] + nums[i -1]);
return max(dp[n], r1);
}
1 : Method Definition
introb(vector<int>& nums) {
The method definition for the 'rob' function, which takes a vector of integers as input.
2 : Variable Initialization
int n = nums.size();
Initializes a variable 'n' to store the size of the input vector 'nums'.
3 : Conditional Statement
if(n ==1) return nums[0];
Checks if there's only one house. If so, return its value as it is the only option.
4 : Array Initialization
vector<int> dp(n, 0);
Initializes a dynamic programming array 'dp' of size 'n' with all elements set to 0.
5 : Assignment
dp[0] =0;
Sets the first element of 'dp' to 0, as no money can be robbed from the first house.
6 : Assignment
dp[1] = nums[0];
Sets the second element of 'dp' to the value of the first house, since it’s the first valid option.
7 : Loop Iteration
for(int i =2; i < n; i++)
Begins a loop from index 2 to 'n', iterating over the houses to calculate the maximum money that can be robbed.
8 : Array Manipulation
dp[i] = max(dp[i -1], dp[i -2] + nums[i -1]);
For each house, we decide whether to rob it (i.e., add its value to the result of robbing up to house 'i-2') or skip it (i.e., keep the value from 'i-1').
9 : Variable Assignment
int r1 = dp[n -1];
Stores the final result of the first dynamic programming sequence (up to house 'n-1').
10 : Array Resize
dp.resize(n +1, 0);
Resizes the 'dp' array to accommodate one more element and initializes the new values to 0.
11 : Assignment
dp[1] =0;
Sets the second element of the resized 'dp' array to 0, representing no money robbed from the first house.
12 : Assignment
dp[2] = nums[1];
Sets the third element of 'dp' to the value of the second house.
13 : Loop Iteration
for(int i =3; i < n +1; i++)
Begins another loop, this time starting from house 3 (after resizing the array) to calculate maximum money that can be robbed.
14 : Array Manipulation
dp[i] = max(dp[i -1], dp[i -2] + nums[i -1]);
As before, we update 'dp' based on whether we rob the current house or not.
15 : Return Statement
returnmax(dp[n], r1);
Returns the maximum value between the results of the two dynamic programming sequences.
Best Case: O(n), where n is the length of the nums array.
Average Case: O(n), since we iterate over the array twice for the two cases.
Worst Case: O(n), where n is the length of the nums array.
Description: The algorithm processes each element of the array once for each of the two cases, making the time complexity linear in terms of the number of houses.
Best Case: O(n), as space is used to store the results of subproblems.
Worst Case: O(n), due to the space used for the dynamic programming table.
Description: The space complexity is linear because we store results for subproblems in an array of size n.
