codaBack to Academy
dynamic programming
House Robber
The House Robber problem asks for the maximum amount of money that can be robbed from a row of houses without robbing two adjacent houses. A 1D DP table is built where dp[i] represents the maximum money obtainable from the first i houses. At each house, the robber decides whether to skip it or rob it and add its value to the best result from two houses back. This is a classic example of a DP problem with a simple recurrence relation.
Use Cases
- •Scheduling non-conflicting jobs to maximize profit
- •Selecting non-adjacent elements for maximum sum in arrays
- •Resource allocation where consecutive selections are forbidden
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n) | O(n) | O(n) |
| Space | O(n) | ||
Visualization
| F(0) | F(1) | F(2) | F(3) | F(4) | F(5) | F(6) | F(7) | F(8) | F(9) | F(10) | |
|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Implementation
Output
Click "Run Code" to see output...