Lesson

14.4House Robber

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, and the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected. It will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1

Input: nums = [1,2,3,1]
Output: 4
Explanation:
Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2

Input: nums = [2,7,9,3,1]
Output: 12
Explanation:
Rob house 1 (money = 2), rob house 3 (money = 9), and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 400

Approach

a. Brute Force (Recursive)

Steps:

Understand the Problem:
- You cannot rob two adjacent houses.
- You need to maximize the total amount of money robbed.
Identify Choices:
- For each house, decide whether to rob it or not.
Recursive Exploration:
- If you rob the current house, you cannot rob the next one.
- If you don't rob the current house, you can consider robbing the next one.
Base Cases:
- If there are no houses left (index >= nums.length), return 0.
Implementation:
- Implement a recursive function that explores both choices at each step and returns the maximum amount achievable.

Time & Space Complexity:

Time Complexity: O(2ⁿ)
Each house has two choices (rob or not rob), leading to an exponential number of possibilities.
Space Complexity: O(n)
The recursion stack can go as deep as the number of houses.

Code Snippet:

Dry Run:

Let's perform a dry run for nums = [1, 2, 3, 1].

So, the maximum amount of money you can rob is 4.

b. Optimized Approach (Dynamic Programming - Memoization)

Steps:

Understand the Problem:
- Same as brute force, but aim to optimize by avoiding redundant calculations.
Identify Overlapping Subproblems:
- The recursive calls for the same indices are repeated.
Memoization:
- Store the results of subproblems in a memo object.
- Before computing the result for an index, check if it's already in the memo.
Implementation:
- Modify the brute force recursive function to include a memoization mechanism.

Time & Space Complexity:

Time Complexity: O(n)
Each house's result is computed once and stored.
Space Complexity: O(n)
The memo object stores results for each house, and the recursion stack can go as deep as the number of houses.

Code Snippet:

Dry Run:

Let's perform a dry run for nums = [2, 7, 9, 3, 1].

So, the maximum amount of money you can rob is 12.

Complexity Analysis

Brute Force Time & Space:
- Time Complexity: O(2ⁿ)
  The recursive solution explores all possible combinations of robbing or not robbing each house, leading to an exponential number of function calls.
- Space Complexity: O(n)
  The recursion stack can go as deep as the number of houses, requiring linear space.
Optimized Time & Space (Memoization):
- Time Complexity: O(n)
  Each house's maximum rob amount is computed once and stored in the memo, eliminating redundant calculations.
- Space Complexity: O(n)
  The memo object stores the result for each house, and the recursion stack can still go as deep as the number of houses.

Conclusion

When faced with problems like the House Robber, it's essential to analyze and choose the most effective approach based on the problem's constraints and requirements.

Brute Force (Recursive):
- Pros:
  - Simple and easy to implement.
  - Good for understanding the problem's fundamental structure.
- Cons:
  - Highly inefficient for larger inputs due to its exponential time complexity.
  - Redundant calculations make it impractical for real-world scenarios.
Optimized Approach (Dynamic Programming - Memoization):
- Pros:
  - Significantly reduces time complexity by storing and reusing results of subproblems.
  - Efficient and scalable for larger inputs.
- Cons:
  - Requires additional space for the memoization storage.
  - Slightly more complex to implement compared to the brute force method.

Key Takeaways:

Brute Force methods are straightforward and useful for small input sizes or as a starting point to understand the problem.
Dynamic Programming (Memoization) enhances the brute force approach by eliminating redundant computations, making it suitable for larger and more complex problems.
Always assess whether a problem has an optimal substructure and overlapping subproblems, which are indicators that Dynamic Programming can be effectively applied.
Choosing the right problem-solving technique not only improves the efficiency of your solution but also demonstrates a deeper understanding of algorithmic principles, which is crucial for programming and technical interviews.

Previous Next