Search for a command to run...
What it teaches: Take-or-skip: dp[i] = max(dp[i − 1], dp[i − 2] + nums[i]).
Practise it on judges as “House Robber”.
Rob houses along a street for the most money without robbing two adjacent houses.
Example 1
Input: nums = [2, 7, 9, 3, 1] Output: 12
Constraints
Pattern clues in the wording
These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.
Stuck? Take one hint at a time
class Solution {
public int rob(int[] nums) {
return 0;
}
}Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Test cases
| # | Input | Expected |
|---|---|---|
| 1 | nums = [1,2,3,1] | 4 |
| 2 | nums = [2,7,9,3,1] | 12 |
+ 1 hidden test the code runner will check
From slow to fast
prev2, prev1; cur = max(prev1, prev2 + x).
class Solution {
public int rob(int[] nums) {
int prev2 = 0, prev1 = 0;
for (int x : nums) {
int cur = Math.max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}Verdict: The template for this family.
Before you submit
Test these inputs
Mistakes people make
Interview
What if houses form a binary tree (House Robber III)?