House Robber
Choose nonadjacent houses along a street to maximize the collected money. You may skip every house.
Work through the cases
3 examplesInput notation
Nonnegative house values separated by spaces.Expected result
The maximum total.Case 1
Input
2 7 9 3 1
Expected output
12
Case 2
Input
4 1 2
Expected output
6
Case 3
Input
0
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Adjacent houses cannot both be robbed; maximize the take. Subset enumeration must enforce the gap, and overlapping suffixes repeat. From index i, rob and skip to i+2, or skip to i+1, and take the better. Memoization evaluates each index once.
We design a function dfs(i), which represents the maximum amount of money that can be stolen starting from the i-th house. Thus, the answer is dfs(0).
The execution process of the function dfs(i) is as follows:
- If i ≥ len(nums), it means all houses have been considered, and we directly return 0; - Otherwise, consider stealing from the i-th house, then dfs(i) = nums[i] + dfs(i+2); if not stealing from the i-th house, then dfs(i) = dfs(i+1). - Return \max(nums[i] + dfs(i+2), dfs(i+1)).
To avoid repeated calculations, we use memoization search. The result of dfs(i) is saved in an array or hash table. Before each calculation, we first check if it has been calculated. If so, we directly return the result.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
class Solution {
private Integer[] f;
private int[] nums;
public int rob(int[] nums) {
this.nums = nums;
f = new Integer[nums.length];
return dfs(0);
}
private int dfs(int i) {
if (i >= nums.length) {
return 0;
}
if (f[i] == null) {
f[i] = Math.max(nums[i] + dfs(i + 2), dfs(i + 1));
}
return f[i];
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.