Dynamic Programming • 1D Arrays

House Robber

Find the maximum amount of money you can rob from a row of houses without alerting the police (no two adjacent houses).

Overview

This is a foundational 1D DP problem. You are iterating through an array, and at each step, you must make a choice: take the current element or skip it.

The Constraint

The core rule is you cannot take adjacent elements. This directly forms the recurrence relation.

Recurrence Relation

At house `i`, you can either: 1) Rob it, meaning you must add its value to `dp[i-2]`. 2) Skip it, meaning you keep the max from `dp[i-1]`. `dp[i] = max(nums[i] + dp[i-2], dp[i-1])`.

Space Optimization

Because `dp[i]` only depends on `dp[i-1]` and `dp[i-2]`, you only need two variables to track the state, reducing space complexity to O(1).

i=0$2

i=1$7

i=2$9

i=3$3

i=4$1

DP Array (Max Money)

0

Code Tracker

:::

1if (nums.length === 0) return 0;

2if (nums.length === 1) return nums[0];

3let dp = new Array(nums.length).fill(0);

4dp[0] = nums[0];

5dp[1] = Math.max(nums[0], nums[1]);

6for (let i = 2; i < nums.length; i++) {

7 dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);

8}

9return dp[nums.length - 1];