Problem Statement
Neighborhood Heist
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 array of non-negative integers nums representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Examples
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
Problem Breakdown
To solve this problem, we need to:
- This is a classic dynamic programming problem where we need to decide whether to rob the current house or skip it.
- If we rob the current house, we can't rob the previous one, so we add the current house's value to the maximum amount we could rob from houses before the previous one.
- If we skip the current house, the maximum amount remains the same as the maximum amount we could rob from houses up to the previous one.
- At each house, we choose the option that gives us the maximum amount.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Neighborhood Heist
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 array of non-negative integers nums representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Examples
Example 1:
Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 2:
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.
Problem Breakdown
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
Key Insights:
This is a classic dynamic programming problem where we need to decide whether to rob the current house or skip it.
If we rob the current house, we can't rob the previous one, so we add the current house's value to the maximum amount we could rob from houses before the previous one.
If we skip the current house, the maximum amount remains the same as the maximum amount we could rob from houses up to the previous one.
At each house, we choose the option that gives us the maximum amount.
Real-World Application
This problem has several practical applications:
Resource Allocation
Deciding how to allocate resources when there are constraints on adjacent resources.
Event Scheduling
Scheduling events when there are constraints on consecutive time slots.
Security Planning
Planning security measures when there are constraints on adjacent locations.