DSA problem
House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed; you are given a non-negative integer array nums where nums[i] is the money at house i. The only constraint stopping you is that adjacent houses have connected security systems — if two adjacent houses are broken into on the same night, the police will be alerted. Return the maximum amount of money you can rob without alerting the police.
This is the prototypical "decide-or-skip" 1-D DP. At every house i you face a binary choice: either rob it (and add nums[i] to whatever you had through house i - 2), or skip it (carrying through the best total achievable up to i - 1). The recurrence is dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]), with base cases dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).
A naive recursion rob(i) = max(rob(i - 1), rob(i - 2) + nums[i]) branches at every house, giving O(2^n) time. Memoization brings it down to O(n) time and O(n) space. Iterative tabulation reaches the same bound without recursion overhead.
The optimal solution exploits the fact that dp[i] looks back only two positions, so we keep two rolling variables and update them in lockstep. The final answer sits in the second variable, achieved in O(n) time with O(1) extra space — the textbook space-optimized 1-D DP pattern.
Examples
nums = [1,2,3,1]4nums = [2,7,9,3,1]12nums = [2,1,1,2]4Constraints
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
- Robbing two adjacent houses is forbidden.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.