House Robber
Problem Description
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and 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 <= 1000 <= nums[i] <= 400
Solve it on LeetCode
Approaches
1. Recursive Approach
The problem of robbing houses can be thought of as making a choice at each house: either you rob it or you skip it. The base problem is that you cannot rob two consecutive houses.
We can define a recursive function robFrom(int i) which returns the maximum amount of money that can be robbed starting from house i. The decision at each house will be:
- Rob the current house
iand skip the next housei+1. - Do not rob the current house
iand try to rob from housei+1.
This will be a naive solution with exponential time complexity, but it establishes the foundation of the problem.
Code:
- Time Complexity: O(2^n) — In the worst case, where
nis the number of houses. - Space Complexity: O(n) — The depth of the recursion tree can go up to
n.
2. Memoization (Top-Down DP)
To optimize the recursive approach, we can use memoization to store the results of the subproblems that we've already solved, preventing re-calculation and reducing the time complexity from exponential to linear.
Code:
- Time Complexity: O(n) — Each house is visited at most once.
- Space Complexity: O(n) — Due to recursion and memo array.
3. Bottom-Up Dynamic Programming
We can reformulate the problem iteratively using a bottom-up dynamic programming approach. We'll systematically determine the best choice at each house leading up to the final decision.
Code:
- Time Complexity: O(n) — Only one pass through the list is needed.
- Space Complexity: O(n) — For the DP array.
4. Optimized Space Dynamic Programming
We can further optimize the space complexity by realizing that at any point, we only need the last two states to make our decision.
Code:
- Time Complexity: O(n) — Once through the list.
- Space Complexity: O(1) — Constant space usage.