House Robber
Problem
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.
nums = [3, 8, 4, 9, 2]17def rob(nums):
n = len(nums)
if n == 0: return 0
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
skip = dp[i - 1]
take = (dp[i - 2] if i >= 2 else 0) + nums[i]
dp[i] = max(skip, take)
return dp[-1]function rob(nums) {
const n = nums.length;
if (n === 0) return 0;
const dp = new Array(n).fill(0);
dp[0] = nums[0];
for (let i = 1; i < n; i++) {
const skip = dp[i - 1];
const take = (i >= 2 ? dp[i - 2] : 0) + nums[i];
dp[i] = Math.max(skip, take);
}
return dp[n - 1];
}class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
int skip = dp[i - 1];
int take = (i >= 2 ? dp[i - 2] : 0) + nums[i];
dp[i] = Math.max(skip, take);
}
return dp[n - 1];
}
}int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 0);
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
int skip = dp[i - 1];
int take = (i >= 2 ? dp[i - 2] : 0) + nums[i];
dp[i] = max(skip, take);
}
return dp[n - 1];
}Explanation
You want the biggest total of money from a row of houses, but you can't rob two houses next to each other. At every house the only question is: take it or skip it.
We build a table where dp[i] = the most money robbable considering houses 0..i. The recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
That formula captures the two choices: skip house i and keep the best so far dp[i-1], or take house i, which forces skipping i-1, so add nums[i] to dp[i-2]. We pick whichever is bigger.
Example: nums = [3, 8, 4, 9, 2]. Working left to right, the table settles so that picking houses 1 and 3 (8 + 9 = 17) beats every other non-adjacent combination, and dp[4] = 17.
The final answer is the last cell dp[n-1]. It only needs the previous two values, so it can be trimmed to O(1) space.