# 198. House Robber
LeetCode problem link (opens new window)
You are a professional thief planning to rob houses along a street. Each house contains a certain amount of cash, and the only constraint stopping you from robbing each of them is that adjacent houses have a connected security system, and if two adjacent houses are broken into on the same night, the system will automatically trigger an alarm.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without triggering an alarm.
- Example 1:
- Input: [1,2,3,1]
- Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). The maximum amount of money robbed = 1 + 3 = 4.
- Example 2:
- Input: [2,7,9,3,1]
- Output: 12 Explanation: Rob house 1 (money = 2), house 3 (money = 9), then rob house 5 (money = 1). Maximum amount of money robbed = 2 + 9 + 1 = 12.
Constraints:
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 400
# Thought Process
If you're new to this type of problem, you might be confused: should I rob the current house or not?
After some thought, the decision to rob the current house depends on whether the previous house and the house before last were robbed.
This suggests that the current state has a dependency relationship with previous states, forming a recurrence relation typical in dynamic programming.
To further explain, "House Robber" is a classic problem that can be solved using dynamic programming. Let's use a five-step approach as follows:
- Define the dp array and the meaning of its indices
dp[i]: The maximum amount of money that can be robbed from houses up to and including index i.
- Define the recurrence relation
The value of dp[i] depends on whether the i-th house is robbed or not.
If the i-th house is robbed, dp[i] = dp[i - 2] + nums[i], meaning that house i-1 is definitely not considered, and you find the maximum amount that can be robbed from houses up to and including index i-2, plus the money from robbing house i.
If the i-th house is not robbed, dp[i] = dp[i - 1], meaning you consider house i-1 (note this means consideration, not necessarily robbing i-1, which is a common point of confusion).
Then dp[i] takes the maximum value, i.e., dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);.
- Initialize the dp array
From the recurrence relation dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);, it follows that the base cases are dp[0] and dp[1].
From the definition of dp[i], dp[0] must be nums[0], and dp[1] is the maximum of nums[0] and nums[1]: dp[1] = max(nums[0], nums[1]);.
The code is as follows:
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
2
3
- Determine the order of traversal
Because dp[i] is derived from dp[i - 2] and dp[i - 1], we must traverse from front to back!
The code is as follows:
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
2
3
- Example to derive the dp array
Take Example 2, input [2,7,9,3,1] as an example.
The result is in the red box dp[nums.size() - 1].
Having completed the above analysis, the C++ code is as follows:
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.size() - 1];
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
- Time complexity: O(n)
- Space complexity: O(n)
# Summary
"House Robber" is a basic question solved by dynamic programming, and it's the introductory level for this problem type. We will explore it further through various variations in the future.
# Other Language Versions
# Java:
// Dynamic programming
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
// Using the concept of rolling array to optimize space
// By analyzing this problem, we find that the result only depends on the previous two states. In this case, the space complexity can be reduced to 3 spaces using the concept of rolling arrays.
class Solution {
public int rob(int[] nums) {
int len = nums.length;
if (len == 0) return 0;
else if (len == 1) return nums[0];
else if (len == 2) return Math.max(nums[0],nums[1]);
int[] result = new int[3]; // Store selected results
result[0] = nums[0];
result[1] = Math.max(nums[0],nums[1]);
for(int i = 2;i<len;i++){
result[2] = Math.max(result[0]+nums[i],result[1]);
result[0] = result[1];
result[1] = result[2];
}
return result[2];
}
}
// Further optimize the rolling array's space usage. dp array only stores the two results related to the current calculation.
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
// Initialize the dp array
// Optimize space usage: the dp array only needs two slots, just the two results related to the current calculation
int[] dp = new int[2];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
int res = 0;
// Loop through the array
for (int i = 2; i < nums.length; i++) {
res = Math.max((dp[0] + nums[i]) , dp[1] );
dp[0] = dp[1];
dp[1] = res;
}
// Return the result
return dp[1];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# Python:
1D DP
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0: # If there are no houses, return 0
return 0
if len(nums) == 1: # If there is only one house, return its amount
return nums[0]
# Create a dynamic programming array to store the maximum amounts
dp = [0] * len(nums)
dp[0] = nums[0] # Set the first element of dp as the amount of the first house
dp[1] = max(nums[0], nums[1]) # Set the second element of dp as the larger amount of the first and second houses
# Traverse through the remaining houses
for i in range(2, len(nums)):
# For each house, choose the maximum amount between robbing the current house and robbing the previous one
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[-1] # Return the maximum amount that can be robbed from the last house
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2D DP
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: # If there are no houses, return 0
return 0
n = len(nums)
dp = [[0, 0] for _ in range(n)] # Create a 2D dynamic programming array, dp[i][0] represents the maximum amount not robbing house i, dp[i][1] represents the maximum amount robbing house i
dp[0][1] = nums[0] # The maximum amount of robbing the first house is the amount of the first house
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) # Not robbing house i, the maximum amount is the larger of robbing and not robbing the previous house
dp[i][1] = dp[i-1][0] + nums[i] # Robbing house i, the maximum amount is the maximum amount of not robbing the previous house plus the amount of the current house
return max(dp[n-1][0], dp[n-1][1]) # Return the maximum amount that can be robbed from the last house
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Optimize Version
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: # If there are no houses, return 0
return 0
prev_max = 0 # Maximum amount from the previous house
curr_max = 0 # Maximum amount from the current house
for num in nums:
temp = curr_max # Temporary variable to save the maximum amount from the current house
curr_max = max(prev_max + num, curr_max) # Update the maximum amount from the current house
prev_max = temp # Update the maximum amount from the previous house
return curr_max # Return the maximum amount that can be robbed from the last house
2
3
4
5
6
7
8
9
10
11
12
13
14
# Go:
func rob(nums []int) int {
n := len(nums)
dp := make([]int, n+1) // dp[i] indicates the maximum amount stolen by the i-th house
dp[1] = nums[0]
for i := 2; i <= n; i++ {
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
}
return dp[n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# JavaScript:
const rob = nums => {
// Length of the array
const len = nums.length;
// Initialize the dp array
const dp = [nums[0], Math.max(nums[0], nums[1])];
// Traverse from index 2
for (let i = 2; i < len; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[len - 1];
};
2
3
4
5
6
7
8
9
10
11
# TypeScript:
function rob(nums: number[]): number {
/**
dp[i]: The maximum amount that can be robbed from the first i houses
dp[0]: nums[0];
dp[1]: max(nums[0], nums[1]);
...
dp[i]: max(dp[i-1], dp[i-2]+nums[i]);
*/
const length: number = nums.length;
if (length === 1) return nums[0];
const dp: number[] = [];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[length - 1];
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# C
#define max(a, b) ((a) > (b) ? (a) : (b))
int rob(int* nums, int numsSize) {
if(numsSize == 0){
return 0;
}
if(numsSize == 1){
return nums[0];
}
// dp array initialization
int dp[numsSize];
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < numsSize; i++){
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[numsSize - 1];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Rust:
impl Solution {
pub fn rob(nums: Vec<i32>) -> i32 {
if nums.len() == 1 {
return nums[0];
}
let mut dp = vec![0; nums.len()];
dp[0] = nums[0];
dp[1] = nums[0].max(nums[1]);
for i in 2..nums.len() {
dp[i] = (dp[i - 2] + nums[i]).max(dp[i - 1]);
}
dp[nums.len() - 1]
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14