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.
Key Insights
- You cannot rob two adjacent houses due to the security systems.
- The problem can be solved using dynamic programming to keep track of the maximum money that can be robbed up to each house.
- At each house, you have two choices: either to rob it or skip it, leading to a decision tree.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
The problem can be approached using dynamic programming. We will maintain two variables to keep track of the maximum amount of money that can be robbed up to the previous house and the house before that. For each house, we decide whether to rob it or not based on the maximum amount we could have robbed by either skipping the current house or robbing it. Specifically, we use the relation:
maxRobbed[i] = max(maxRobbed[i-1], nums[i] + maxRobbed[i-2])
This leads to an efficient solution with constant space usage.