These are the notes for DSA episode 63. Last episode's DP had no choice to make; today every item has one: take it or skip it. A volunteer collects festival donations on one street but can never visit two next-door houses on the same evening. The take-or-skip recursion is correct but Time Limit Exceeded on 100 houses; two greedy rules (every other house, biggest first) give 3 instead of 4 and 4 instead of 6. The DP recipe gives dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]), which shrinks to two variables, and House Robber II (houses in a circle) becomes two straight-line problems. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real.
The problem, in real life
A volunteer collects pledged donations for a festival on one street, in one evening. If she visits two houses next door to each other, the neighbours compare notes and both back out. Which houses should she visit to collect the most? LeetCode tells the same story with a robber, so the problem is called House Robber.
| On the street | In code |
|---|---|
House i's pledge |
nums[i] |
| Next-door houses | indexes i and i + 1 |
| Visit / don't visit | take / skip |
Best total from the first i houses |
dp[i] |
| Houses around a square | House Robber II (a circle) |
Every word, from zero
- Adjacent: next to each other (indexes differ by 1).
- Take or skip: the two choices at every item; the core of many DP problems (knapsack next).
- State:
dp[i]= the most we can collect from the firstihouses (nums[0..i-1]). - Recurrence: from the last house: skip it (
dp[i - 1]) or take it (nums[i - 1] + dp[i - 2]). - Greedy: a rule that commits now; here every greedy rule fails.
- Suffix: the houses from some index to the end; the brute force re-solves the same suffixes.
- Circular array: the last element is next to the first.
- O(1) space: a fixed number of variables, whatever
nis.
Problem statement
LeetCode 198, House Robber. nums[i] is the money at house i. You can't take two adjacent houses. Return the maximum total.
| nums | Answer | Houses taken |
|---|---|---|
[1, 2, 3, 1] |
4 |
1 + 3 |
[2, 7, 9, 3, 1] |
12 |
2 + 9 + 1 |
Constraints: 1 ≤ nums.length ≤ 100, 0 ≤ nums[i] ≤ 400.
Obvious idea: take or skip, recursively
import java.util.*;
public class Main {
static int rob(int[] nums) {
return best(nums, 0);
}
static int best(int[] nums, int i) {
if (i >= nums.length) return 0;
int take = nums[i] + best(nums, i + 2);
int skip = best(nums, i + 1);
return Math.max(take, skip);
}
public static void main(String[] args) {
System.out.println(rob(new int[]{1, 2, 3, 1}));
System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
}
}
4
12
On 100 random houses: Time Limit Exceeded. The call count grows like Fibonacci numbers: best(i) calls best(i + 1) and best(i + 2), and the same suffixes are solved again and again.
Two greedy traps
import java.util.*;
public class Main {
static int everyOther(int[] nums) {
int even = 0, odd = 0;
for (int i = 0; i < nums.length; i++) {
if (i % 2 == 0) even += nums[i];
else odd += nums[i];
}
return Math.max(even, odd);
}
static int biggestFirst(int[] nums) {
int n = nums.length, total = 0;
boolean[] blocked = new boolean[n];
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> nums[b] - nums[a]);
for (int i : order)
if (!blocked[i]) {
total += nums[i];
if (i > 0) blocked[i - 1] = true;
if (i + 1 < n) blocked[i + 1] = true;
}
return total;
}
public static void main(String[] args) {
System.out.println("every other: " + everyOther(new int[]{2, 1, 1, 2}));
System.out.println("biggest first: " + biggestFirst(new int[]{3, 4, 3}));
}
}
every other: 3
biggest first: 4
[2, 1, 1, 2]: take the first and last houses for 4 (one even index, one odd). [3, 4, 3]: skip the 4 and take both 3s for 6.
The key insight: the DP recipe
- State:
dp[i]= most from the firstihouses. - Recurrence: house
i(that'snums[i - 1]) is skipped →dp[i - 1]; or taken →nums[i - 1] + dp[i - 2].dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]) - Base cases:
dp[0] = 0,dp[1] = nums[0]. - Order:
i = 2 … n; answerdp[n].
By hand on [2, 7, 9, 3, 1]:
| i | house value | skip dp[i-1] |
take nums[i-1] + dp[i-2] |
dp[i] |
|---|---|---|---|---|
| 0 | 0 | |||
| 1 | 2 | 2 | ||
| 2 | 7 | 2 | 7 + 0 = 7 | 7 |
| 3 | 9 | 7 | 9 + 2 = 11 | 11 |
| 4 | 3 | 11 | 3 + 7 = 10 | 11 |
| 5 | 1 | 11 | 1 + 11 = 12 | 12 |
Solution in Java: the table
import java.util.*;
public class Main {
static int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];
dp[1] = nums[0];
for (int i = 2; i <= n; i++)
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
return dp[n];
}
public static void main(String[] args) {
System.out.println(rob(new int[]{1, 2, 3, 1}));
System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
System.out.println(rob(new int[]{2, 1, 1, 2}));
System.out.println(rob(new int[]{3, 4, 3}));
System.out.println(rob(new int[]{5}));
}
}
4
12
4
6
5
The 100 houses that timed out: 11847 rupees, 0 ms.
Top-down: the recursion plus a notebook
The slow recursion was only forgetful. memo[i] = best from house i to the end; -1 means unknown (0 can be a real answer).
import java.util.*;
public class Main {
static int[] memo;
static int rob(int[] nums) {
memo = new int[nums.length];
Arrays.fill(memo, -1);
return best(nums, 0);
}
static int best(int[] nums, int i) {
if (i >= nums.length) return 0;
if (memo[i] != -1) return memo[i];
int take = nums[i] + best(nums, i + 2);
int skip = best(nums, i + 1);
memo[i] = Math.max(take, skip);
return memo[i];
}
public static void main(String[] args) {
System.out.println(rob(new int[]{1, 2, 3, 1}));
System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
int[] nums = new int[100];
Random rnd = new Random(7);
for (int i = 0; i < 100; i++) nums[i] = rnd.nextInt(401);
long t0 = System.nanoTime();
int total = rob(nums);
System.out.println(total + " rupees, " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
4
12
11847 rupees, 0 ms
Which houses? Walk the table backwards
import java.util.*;
public class Main {
static void plan(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];
dp[1] = nums[0];
for (int i = 2; i <= n; i++)
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
System.out.println("dp = " + Arrays.toString(dp));
List<Integer> houses = new ArrayList<>();
for (int i = n; i >= 1; ) {
if (i >= 2 && dp[i] == dp[i - 1]) i--;
else { houses.add(0, i); i -= 2; }
}
System.out.println("visit houses " + houses + ", total " + dp[n]);
}
public static void main(String[] args) {
plan(new int[]{2, 7, 9, 3, 1});
plan(new int[]{2, 1, 1, 2});
}
}
dp = [0, 2, 7, 11, 11, 12]
visit houses [1, 3, 5], total 12
dp = [0, 2, 2, 3, 4]
visit houses [1, 4], total 4
Two variables: O(1) space
import java.util.*;
public class Main {
static 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;
}
public static void main(String[] args) {
System.out.println(rob(new int[]{1, 2, 3, 1}));
System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
}
}
4
12
On ten lakh houses: 1000000 houses: 117346025 rupees, 16 ms (times vary). (With values ≤ 400 and n ≤ 100, int is plenty for LeetCode; ten lakh houses still fit under 2³¹ here, but use long for bigger totals.)
House Robber II (LeetCode 213): houses in a circle
The first and last houses are neighbours. Never both, so solve two ordinary streets, without the last and without the first, and take the better. One house is a special case (both streets would be empty).
| nums | Answer |
|---|---|
[2, 3, 2] |
3 |
[1, 2, 3, 1] |
4 |
[1, 2, 3] |
3 |
import java.util.*;
public class Main {
static int robLine(int[] nums, int from, int to) {
int prev2 = 0, prev1 = 0;
for (int i = from; i <= to; i++) {
int cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
static int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
}
public static void main(String[] args) {
System.out.println(rob(new int[]{2, 3, 2}));
System.out.println(rob(new int[]{1, 2, 3, 1}));
System.out.println(rob(new int[]{1, 2, 3}));
System.out.println(rob(new int[]{5}));
}
}
3
4
3
5
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
// House Robber (LeetCode 198) and House Robber II (LeetCode 213): take or skip, two variables.
int robLine(const vector<int>& nums, int from, int to) {
int prev2 = 0, prev1 = 0;
for (int i = from; i <= to; i++) {
int cur = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
int rob(const vector<int>& nums) { return robLine(nums, 0, (int)nums.size() - 1); }
int robCircle(const vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
return max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
}
int main() {
cout << rob({1, 2, 3, 1}) << " " << rob({2, 7, 9, 3, 1}) << " " << rob({2, 1, 1, 2}) << " " << rob({3, 4, 3}) << "\n";
cout << robCircle({2, 3, 2}) << " " << robCircle({1, 2, 3, 1}) << " " << robCircle({1, 2, 3}) << " " << robCircle({5}) << "\n";
}
4 12 4 6
3 4 3 5
The same solutions in Python
# House Robber (LeetCode 198) and House Robber II (LeetCode 213).
def rob_line(nums):
prev2 = prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
def rob_circle(nums):
if len(nums) == 1:
return nums[0]
return max(rob_line(nums[:-1]), rob_line(nums[1:]))
print(rob_line([1, 2, 3, 1]), rob_line([2, 7, 9, 3, 1]), rob_line([2, 1, 1, 2]), rob_line([3, 4, 3]))
print(rob_circle([2, 3, 2]), rob_circle([1, 2, 3, 1]), rob_circle([1, 2, 3]), rob_circle([5]))
4 12 4 6
3 4 3 5
Three real bugs
Bug 1: always taking the current house
dp[i] = dp[i - 2] + nums[i - 1]; on [2, 1, 1, 2]:
3
Should be 4. The best from the first i houses doesn't have to include house i: the skip choice is missing.
Bug 2: the circle solved as a line
The two-variable line solution on [2, 3, 2]:
4
It took the first and last houses (2 + 2), which are neighbours on a circle. The answer is 3.
Bug 3: no one-house check on the circle
Without if (n == 1) return nums[0];, on [5]:
0
Both ranges (0..-1 and 1..0) are empty. A single house has no neighbour to clash with: the answer is 5.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Take or skip, recursively | O(1.618ⁿ) | O(n) stack | 100 houses: Time Limit Exceeded |
| Every other / biggest first | O(n) / O(n log n) | O(n) | wrong |
| DP table | O(n) | O(n) | instant |
| Two variables | O(n) | O(1) | 10 lakh houses: 16 ms |
| Circle: two passes | O(n) | O(1) |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Every other house | 3 instead of 4 |
greedy with no proof | DP: take or skip |
| Biggest first | 4 instead of 6 |
greedy with no proof | DP |
Always take house i |
3 instead of 4 |
the skip choice is missing | max(dp[i - 1], …) |
| Circle as a line | 4 instead of 3 |
first and last touch | two lines, take the max |
| Circle, one house | 0 instead of 5 |
both lines empty | if (n == 1) return nums[0] |
dp[1] = nums[1] |
wrong or crash | off-by-one: dp[i] uses nums[i - 1] |
write the state in words first |
Mini project: which houses?
Walk the table backwards to print the houses chosen: if dp[i] == dp[i - 1], house i was skipped; otherwise it was taken and we jump to i - 2.
import java.util.*;
public class Main {
// Mini project: House Robber that also prints which houses were visited.
public static void main(String[] args) {
int[] nums = {2, 7, 9, 3, 1, 8, 4};
int n = nums.length;
int[] dp = new int[n + 1];
dp[1] = nums[0];
for (int i = 2; i <= n; i++) dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
List<Integer> houses = new ArrayList<>();
for (int i = n; i >= 1; ) {
if (i >= 2 && dp[i] == dp[i - 1]) i--;
else { houses.add(0, i); i -= 2; }
}
System.out.println("total " + dp[n] + " from houses " + houses);
}
}
total 19 from houses [1, 3, 6]
Houses 1, 3 and 6 (numbered from 1) hold 2 + 9 + 8 = 19.
Practice
1. Delete and Earn (LeetCode 740). Taking a value x earns x and deletes every x - 1 and x + 1. Maximise the points.
Solution
Add up the points per value: points[x] = x × count(x). Then values x and x + 1 are "adjacent houses": House Robber on points.
import java.util.*;
public class Main {
// Delete and Earn (LeetCode 740): House Robber over the values 0..max.
static int deleteAndEarn(int[] nums) {
int max = Arrays.stream(nums).max().getAsInt();
int[] points = new int[max + 1];
for (int x : nums) points[x] += x;
int prev2 = 0, prev1 = 0;
for (int p : points) {
int cur = Math.max(prev1, prev2 + p);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
public static void main(String[] args) {
System.out.println(deleteAndEarn(new int[]{3, 4, 2}));
System.out.println(deleteAndEarn(new int[]{2, 2, 3, 3, 3, 4}));
}
}
6
9
2. Maximum sum of non-adjacent elements with negatives. Values may be negative and you may take nothing. Hint: the same recurrence works, because skipping is always allowed (dp never goes below 0).
Solution
# Max sum of non-adjacent elements; negatives allowed, empty choice = 0.
def best(nums):
prev2 = prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
print(best([-1, -2, -3]), best([3, -1, 4, -5, 9]), best([-5, 10, -5, 10]))
0 16 20
3. House Robber III (LeetCode 337). Houses form a binary tree; parent and child are adjacent. Hint: for each node return two numbers, (best if taken, best if skipped). Coming in episode 76.
Quick quiz
Houses [5, 1, 1, 5] in a line. Largest total? A) 10 B) 6 C) 11 D) 7
Answer
A) 10. Take the first and last house. dp: 0, 5, 5, 6, 10.
Interview questions
- State and recurrence?
dp[i]= best from the firstihouses;dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]). - Why does greedy fail? A big house can block two medium neighbours worth more together; parity can split the best pair.
- Space? O(1) with two variables, since
dp[i]reads onlydp[i-1]anddp[i-2]. - Circular version? Answer = max(line without the last, line without the first); one house is special.
- How do you recover the chosen houses? Keep the table and walk back: equal to
dp[i-1]means skipped. - Relation to Fibonacci? Same shape of recurrence (two previous states), but with
maxand a value added.
Glossary
| Term | Meaning |
|---|---|
| Adjacent | Next to each other (indexes differ by 1) |
| Take or skip | The two choices at each item |
| State | dp[i] = best from the first i houses |
| Recurrence | dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]) |
| Suffix | The items from some index to the end |
| Circular array | The last element touches the first |
| O(1) space | A fixed number of variables |
Summary
- At each house: take it (
nums[i-1] + dp[i-2]) or skip it (dp[i-1]); keep the max. - Take-or-skip recursion is exponential (Time Limit Exceeded at 100 houses); greedy rules give wrong answers.
- Two variables give O(n) time and O(1) space; a circle is two lines, with one house as a special case.
- Next episode: coin change: the fewest coins and the number of ways.