grid47 Exploring patterns and algorithms
Oct 18, 2024
5 min read
Solution to LeetCode 198: House Robber Problem
You are a burglar planning to rob houses along a street. Each house has an amount of money, but robbing two adjacent houses will trigger an alarm. Given an integer array nums representing the money stashed in each house, find the maximum amount you can rob without triggering the alarm.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of integers where each integer represents the amount of money in each house.
Example: nums = [5, 3, 4, 11]
Constraints:
• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400
Output: The output is the maximum amount of money that can be robbed without triggering the alarm by robbing adjacent houses.
Example: Output = 16
Constraints:
• The output is a single integer representing the maximum amount of money that can be robbed.
Goal: Maximize the total amount of money robbed while ensuring no two adjacent houses are robbed.
Steps:
• Step 1: Use dynamic programming to keep track of the maximum money robbed up to each house.
• Step 2: For each house, calculate the maximum amount by either skipping the house or robbing it and adding its value to the previous non-adjacent house's value.
• Step 3: Return the maximum value at the last house.
Goal: The problem constraints ensure that the input list contains valid house values and its length is manageable.
Steps:
• The length of the input list, `nums`, is between 1 and 100.
• Each value in `nums` is between 0 and 400.
Assumptions:
• The input array is non-empty.
• The values in the input array are valid integers within the given range.
• Input: Input: nums = [5, 3, 4, 11]
• Explanation: The maximum money that can be robbed is 16 by robbing house 1 (5) and house 4 (11). The adjacent houses can't both be robbed, so we skip house 2 and 3.
• Input: Input: nums = [3, 2, 5, 10, 7]
• Explanation: The optimal choice is to rob house 1 (3), house 3 (5), and house 5 (7), yielding a total of 15.
Approach: We can solve this problem using dynamic programming. The idea is to iterate through the houses and keep track of the maximum money we can rob up to each house without robbing two adjacent houses.
Observations:
• This is a typical dynamic programming problem where we need to make decisions based on previous results.
• We can define a dp array where dp[i] represents the maximum money we can rob up to the i-th house.
Steps:
• Step 1: Initialize an array `dp` where dp[i] will store the maximum amount of money that can be robbed from house 0 to house i.
• Step 2: Set dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).
• Step 3: For each subsequent house i, calculate dp[i] as max(dp[i-2] + nums[i], dp[i-1]).
• Step 4: Return dp[n-1], which will hold the maximum amount of money robbed.
Empty Inputs:
• There are no empty inputs, as the problem guarantees at least one house.
Large Inputs:
• The problem's constraints are small enough (up to 100 houses) that large inputs are not a concern.
Special Values:
• If the array contains only one house, we simply rob that house.
Constraints:
• The input will always have at least one house.
introb(vector<int>& a) {
int n = a.size();
if(n ==1) return a[0];
vector<int> dp(n,0);
dp[0] = a[0];
dp[1] = max(a[0], a[1]);
for(int i =2; i < n; i++)
dp[i] = max(dp[i-2]+a[i], dp[i-1]);
return dp[n-1];
}
1 : Function Definition
introb(vector<int>& a) {
Define the function 'rob' which accepts a vector of integers 'a' representing the amount of money in each house, and returns the maximum amount that can be robbed.
2 : Array Size
int n = a.size();
Store the size of the input vector 'a' in the variable 'n', which represents the number of houses.
3 : Edge Case Check
if(n ==1) return a[0];
Check if there is only one house. If so, return the amount in that single house as there are no other houses to consider.
4 : DP Array Initialization
vector<int> dp(n,0);
Initialize a dynamic programming (DP) array 'dp' of size 'n' with all elements set to zero. This array will store the maximum amount that can be robbed up to each house.
5 : Base Case Initialization
dp[0] = a[0];
Set the base case: the maximum amount that can be robbed from just the first house is the amount in the first house itself.
6 : Base Case Comparison
dp[1] = max(a[0], a[1]);
For the second house, the maximum amount that can be robbed is the greater of the first and second house values.
7 : Loop Through Houses
for(int i =2; i < n; i++)
Start a loop from the third house onward to compute the maximum amount that can be robbed by either including or excluding the current house.
8 : DP Update
dp[i] = max(dp[i-2]+a[i], dp[i-1]);
Update the DP array by choosing the maximum between robbing the current house (dp[i-2] + a[i]) or skipping the current house (dp[i-1]).
9 : Return Result
return dp[n-1];
Return the maximum amount that can be robbed from all houses, which is stored in the last element of the DP array.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the input array `nums`. We process each house once.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the dynamic programming array used to store the maximum amounts for each house.
