1-D DP is the simplest form of dynamic programming. The state is a single integer index, and the recurrence reads from one or two earlier entries. The same building blocks (state, recurrence, base cases, iteration order) carry over to every other DP variant: 2-D grids, trees, intervals, bitmasks.

In 1-D dynamic programming, we define an array dp where each entry dp[i] represents the answer to some subproblem involving the first i elements (or the element at index i). The value of dp[i] depends on one or more previous entries like dp[i-1], dp[i-2], and so on. There is a single index that grows linearly, and we fill the table from left to right.

DP avoids redundant computation. Instead of solving the same subproblem repeatedly (as naive recursion would), we solve it once, store the result, and look it up when needed. This transforms exponential brute force into an O(n) pass.

Not every problem needs DP, and not every DP problem is 1-D. The signals for a linear DP problem:

1. The input is a sequence (array, string, list of items)

If you are processing elements one by one from left to right, and each element presents a choice, 1-D DP fits.

2. There is an "optimal substructure"

The best answer for the first i elements can be built from the best answer for fewer elements. If solving a smaller version of the problem helps you solve the bigger one, that is optimal substructure.

3. There are overlapping subproblems

A naive recursive approach would solve the same subproblem many times. If you draw the recursion tree and see repeated nodes, DP will help.

4. You face a "take or skip" decision at each step

Many 1-D DP problems boil down to: for each element, do I include it or not? The answer depends on what you chose for previous elements.

Here are the most common categories:

The mechanics of building a 1-D DP solution, step by step.

State Definition

This is the most important decision. You need to answer: "What does dp[i] mean?" A good state definition makes the recurrence obvious. A bad one makes the problem much harder to solve.

For "take or skip" problems, a common definition is:

For "counting ways" problems:

The state definition should capture enough information so that you can compute dp[i] purely from earlier dp values, without needing to re-examine the original input in a complicated way.

Recurrence Relation

Once you have the state, the recurrence describes how to compute dp[i] from previous entries. For the classic "take or skip" pattern:

Every problem has its own recurrence, but the take-or-skip structure appears often.

Base Cases

Base cases are the entries you can fill directly without the recurrence. Typically these are dp[0] and dp[1] (or sometimes just dp[0]). Getting these right is critical, because every subsequent value builds on them.

Top-Down vs Bottom-Up

A 1-D DP problem can be solved either way. Top-down recursion with memoization mirrors the recurrence directly: define solve(i), cache results in a memo. Bottom-up tabulation fills dp[i] from the base cases forward. Both forms appear in the House Robber walkthrough below.

Space Optimization

In many 1-D DP problems, dp[i] only depends on dp[i-1] and dp[i-2]. You do not need the entire array, only two variables.

This reduces space from O(n) to O(1), which is a common follow-up: showing that only two previous values are needed.

Problem Statement

You are a robber planning to rob houses along a street. Each house has a certain amount of money stashed. The constraint is that adjacent houses have connected security systems, so robbing two consecutive houses will alert the police.

Given an integer array nums where nums[i] represents the amount of money at house i, return the maximum amount you can rob without triggering the alarm.

Constraints:

Intuition

This is the "take or skip" pattern from earlier. If you rob house i, you cannot rob house i-1, so the best you can do is nums[i] plus the best up through house i-2. If you skip house i, the best is whatever you had up through house i-1.

Step-by-Step Trace

Tracing the algorithm on nums = [2, 7, 9, 3, 1]:

The optimal strategy is to rob houses with values 2, 9, and 1, for a total of 12. We did not pick the top individual values. We picked the combination that avoids adjacency while maximizing the total.

Implementation: Top-Down (Memoized Recursion)

The recursive form follows directly from the recurrence: at each index, either rob and skip to i+2, or skip and move to i+1. The memo caches each subproblem once. This is often the version to write first in an interview because it mirrors the brute-force recursion.

Implementation: Bottom-Up (Tabulation)

The bottom-up solution with space optimization:

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once, doing O(1) work at each step. Both the top-down and bottom-up approaches visit each subproblem exactly once.

Space Complexity: O(1) (optimized) or O(n) (basic)

The dp array version uses O(n) space. The two-variable version uses O(1) space since we only track the previous two values. The top-down approach uses O(n) for the memo table plus O(n) for the recursion stack.