1-D DP is usually the first flavor of dynamic programming that people encounter, and for good reason. It builds the core intuition that carries over to every other DP variant: 2-D grids, trees, intervals, bitmasks. Master the ideas in this chapter, and the rest of DP becomes dramatically more approachable.

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. That is what makes it "one-dimensional": there is a single index that grows linearly, and we fill the table from left to right.

The general structure looks like this:

The key insight is that we avoid redundant computation. Instead of solving the same subproblem over and over (as recursion would), we solve it once, store the result, and look it up whenever we need it again. This is what transforms exponential brute force into a clean O(n) pass.

Not every problem needs DP, and not every DP problem is 1-D. Here are the signals that suggest you are looking at 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 is a strong candidate.

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:

Let us break down 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 feel impossible.

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:

This is the heart of 1-D DP. Every problem has its own recurrence, but the take-or-skip structure appears remarkably 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

There are two ways to implement any DP solution:

Top-Down (Memoization): Start from the final state and recurse backwards. Use a memo table to cache results so you never solve the same subproblem twice.

Bottom-Up (Tabulation): Start from the base cases and iterate forward, filling in the dp table entry by entry.

Both approaches have the same time complexity. Top-down can be more intuitive because it mirrors how you think about the problem recursively. Bottom-up avoids recursion overhead and is usually what interviewers expect to see.

Space Optimization

Here is a neat trick. In many 1-D DP problems, dp[i] only depends on dp[i-1] and dp[i-2]. That means you do not need the entire array. You can get away with just two variables.

This reduces space from O(n) to O(1), which is a common follow-up question in interviews. The interviewer wants to see that you understand why only two previous values matter.

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:

Building the Intuition

At each house, you have exactly two choices: rob it or skip it.

If you rob house i, you cannot rob house i-1. So the best you can do is the money from house i plus whatever the best was up through house i-2.

If you skip house i, the best you can do is whatever the best was up through house i-1.

This gives us the state and recurrence directly:

Notice how this is exactly the "take or skip" pattern we discussed earlier. The decision at each house is binary, and the optimal choice depends on the results of earlier subproblems.

Step-by-Step Trace

Let us walk through the algorithm with nums = [2, 7, 9, 3, 1].

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

Implementation

Here is 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.