You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 400
Companies:
Amazon, Microsoft, Google, Cisco, Apple, Adobe, Qualtrics, Arcesium, Bloomberg, Goldman Sachs, ByteDance, eBay, Flipkart, PayTM
Related Topics:
Array, Dynamic Programming
Similar Questions:
- Maximum Product Subarray (Medium)
- House Robber II (Medium)
- Paint House (Medium)
- Paint Fence (Medium)
- House Robber III (Medium)
- Non-negative Integers without Consecutive Ones (Hard)
- Coin Path (Hard)
- Delete and Earn (Medium)
For nums[i], we have two options, rob or skip.
Let rob[i+1] and skip[i+1] be the best outcome we can get with house[0..i] if we rob or skip the house[i] respectively.
rob[i + 1] = nums[i] + skip[i] // If we rob at house[i], we must skip house[i-1]
skip[i + 1] = max(rob[i - 1], skip[i - 1]) // If we skip house[i], we can pick the maximum from robbing or skipping house[i-1]// OJ: https://leetcode.com/problems/house-robber/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int rob(vector<int>& A) {
int N = A.size();
vector<int> rob(N + 1), skip(N + 1);
for (int i = 0; i < N; ++i) {
rob[i + 1] = skip[i] + A[i];
skip[i + 1] = max(skip[i], rob[i]);
}
return max(rob[N], skip[N]);
}
};Space Optimization:
Since rob[i+1] and skip[i+1] are only dependent on rob[i] and skip[i], we can reduce the space complexity to O(1) by only storing the current rob and skip.
So initially we have rob = 0, skip = 0, and for each nums[i], we have
rob2 = nums[i] + skip
skip2 = max(rob, skip)
Then we can assign rob2 back to rob, and skip2 back to skip.
// OJ: https://leetcode.com/problems/house-robber/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int rob(vector<int>& A) {
int rob = 0, skip = 0;
for (int n : A) {
int r = n + skip, s = max(rob, skip);
rob = r, skip = s;
}
return max(rob, skip);
}
};Further more, since skip is the only one required by both rob2 and skip2, we can do the following:
tmp = skip
skip = max(rob, skip)
rob = tmp + nums[i]
// OJ: https://leetcode.com/problems/house-robber/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int rob(vector<int>& nums) {
int rob = 0, skip = 0;
for (int n : nums) {
int tmp = skip;
skip = max(rob, skip);
rob = tmp + n;
}
return max(rob, skip);
}
};Let dp[i] be the best outcome we can get at nums[i].
dp[i] = max(
dp[i - 1], // skip the current house
dp[i - 2] + nums[i] // rob the current house
)
So dp[i] is only dependent on the previous 2 values. We can reduce the space complexity to O(1) by storing the previous two values:
cur = max(
prev,
prev2 + nums[i]
)
// OJ: https://leetcode.com/problems/house-robber/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int rob(vector<int>& nums) {
int prev = 0, prev2 = 0;
for (int n : nums) {
int cur = max(prev, prev2 + n);
prev2 = prev;
prev = cur;
}
return prev;
}
};# OJ: https://leetcode.com/problems/house-robber/
# Author: github.com/lzl124631x
# Time: O(N)
# Space: O(1)
class Solution:
def rob(self, nums: List[int]) -> int:
prev, cur = 0, 0
for n in nums: prev, cur = cur, max(cur, prev + n)
return cur