Problem Statement:
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
Approach:
- Choice at each house (i):
- Either rob house i → then you must skip house i-1, so profit = val[i] + dp[i-2].
- Or i → then profit = dp[i-1]
- Take maximum of the two.
dp[i]=max(val[i]+dp[i−2],dp[i−1])
- Base cases:
- If
n == 0→ return 0 - If
n == 1→ returnval[0] - Initialize:
dp[0] = val[0]dp[1] = max(val[0], val[1])
- If
-
Optimization:
- Notice that to compute
dp[i], we only need the last two states (dp[i-1] and dp[i-2]). - So instead of a full array, we use two variables:
p1→ previous(dp[i-1])- p2 → second previous
(dp[i-2])
- Notice that to compute
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(1)
Dry Run
Input: val = [2, 7, 9, 3, 1]
Step 0: Start Function: rob([2, 7, 9, 3, 1])
n = 5
p1 = 0
p2 = 0
Iteration (i = 0):
- curr = Math.max(val[0] + p2, p1)
= Math.max(2 + 0, 0)
= 2
- temp = p1 = 0
- p1 = curr = 2
- p2 = temp = 0
- curr++ → curr = 3 (but not used further)
State → p1 = 2, p2 = 0
Iteration (i = 1):
- curr = Math.max(val[1] + p2, p1)
= Math.max(7 + 0, 2)
= 7
- temp = p1 = 2
- p1 = curr = 7
- p2 = temp = 2
- curr++ → curr = 8
State → p1 = 7, p2 = 2
Iteration (i = 2):
- curr = Math.max(val[2] + p2, p1)
= Math.max(9 + 2, 7)
= 11
- temp = p1 = 7
- p1 = curr = 11
- p2 = temp = 7
- curr++ → curr = 12
State → p1 = 11, p2 = 7
Iteration (i = 3):
- curr = Math.max(val[3] + p2, p1)
= Math.max(3 + 7, 11)
= 11
- temp = p1 = 11
- p1 = curr = 11
- p2 = temp = 11
- curr++ → curr = 12
State → p1 = 11, p2 = 11
Iteration (i = 4):
- curr = Math.max(val[4] + p2, p1)
= Math.max(1 + 11, 11)
= 12
- temp = p1 = 11
- p1 = curr = 12
- p2 = temp = 11
- curr++ → curr = 13
State → p1 = 12, p2 = 11
Loop ends (i = n)
Step 3: End
Return p1 = 12
Output: 12
Visualisation:
var rob = function(val) {
let n = val.length;
if(n == 1)
return val[0];
let p2 = p1 = 0;
for(let i=0; i < n; i++){
curr = Math.max(val[i] + p2, p1);
let temp = p1;
p1 = curr;
p2 = temp;
curr++;
}
return p1;
};
def rob(val):
n = len(val)
if n == 1:
return val[0]
p1 = p2 = 0
for i in range(n):
curr = max(val[i] + p2, p1)
temp = p1
p1 = curr
p2 = temp
curr += 1
return p1
public class Solution {
public static long rob(int[] val) {
int n = val.length;
if (n == 1) return val[0];
long p1 = 0, p2 = 0;
for (int i = 0; i < n; i++) {
long curr = Math.max((long)val[i] + p2, p1);
long temp = p1;
p1 = curr;
p2 = temp;
curr++;
}
return p1;
}
public static void main(String[] args) {
int[] arr = {2,7,9,3,1};
System.out.println(rob(arr));
}
}
#include <bits/stdc++.h>
using namespace std;
long long rob(const vector& val) {
int n = val.size();
if (n == 1) return val[0];
long long p1 = 0, p2 = 0;
for (int i = 0; i < n; ++i) {
long long curr = max((long long)val[i] + p2, p1);
long long temp = p1;
p1 = curr;
p2 = temp;
curr++;
}
return p1;
}
// Example usage
int main() {
vector v = {2,7,9,3,1};
cout << rob(v) << endl;
return 0;
}
#include <stdio.h>
long long rob(int *val, int n) {
if (n == 1) return val[0];
long long p1 = 0, p2 = 0;
for (int i = 0; i < n; ++i) {
long long candidate1 = (long long)val[i] + p2;
long long curr = candidate1 > p1 ? candidate1 : p1;
long long temp = p1;
p1 = curr;
p2 = temp;
curr++;
}
return p1;
}
int main() {
int arr[] = {2,7,9,3,1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("%lld\n", rob(arr, n));
return 0;
}
using System;
class Solution {
public static long Rob(int[] val) {
int n = val.Length;
if (n == 1) return val[0];
long p1 = 0, p2 = 0;
for (int i = 0; i < n; i++) {
long curr = Math.Max((long)val[i] + p2, p1);
long temp = p1;
p1 = curr;
p2 = temp;
curr++;
}
return p1;
}
static void Main() {
int[] arr = {2,7,9,3,1};
Console.WriteLine(Rob(arr));
}
}
