1D Dynamic Programming

1D dynamic programming uses one main variable to describe each state. The table is usually a list.

It is often the first practical form of dynamic programming to learn.

Core Idea

The state dp[i] might mean the best answer up to index i, the number of ways to reach i, or the answer for a prefix of length i.

The recurrence explains how dp[i] depends on earlier entries such as dp[i - 1] or dp[i - 2].

The most important step is writing the state sentence. For example: “dp[i] is the maximum sum we can get from the first i + 1 values without taking adjacent values.” A precise sentence makes the transition easier to check.

Function Contract

max_non_adjacent_sum(values) expects a list of numbers.

It returns the maximum sum obtainable by choosing values with no two chosen positions adjacent. For an empty list, it returns 0.

Python Example

def max_non_adjacent_sum(values):
    if not values:
        return 0
 
    dp = [0] * len(values)
    dp[0] = values[0]
 
    for i in range(1, len(values)):
        take = values[i] + (dp[i - 2] if i >= 2 else 0)
        skip = dp[i - 1]
        dp[i] = max(take, skip)
 
    return dp[-1]

Each state decides whether to take or skip the current value.

State and Transition

For the example:

dp[i] = best answer considering values[0] through values[i]

At index i, there are two choices:

• Skip values[i], giving dp[i - 1].
• Take values[i], giving values[i] + dp[i - 2].

The recurrence is:

dp[i] = max(dp[i - 1], values[i] + dp[i - 2])

The code is just this recurrence with boundary handling.

Memory Compression

Some 1D DP only needs the previous one or two states. After the full table is understood, it can be compressed:

prev2 = 0
prev1 = 0
for value in values:
    prev2, prev1 = prev1, max(prev1, prev2 + value)

This uses O(1) extra space, but the full table is usually easier to learn first.

Common Confusions

The dimension of the table comes from the state, not from the input type. A list problem can still need 2D DP if the state has two variables.

Some 1D DP tables can be optimized to a few variables, but the full table is often clearer while learning.

Do not choose dp[i] just because the input has an index. Define what dp[i] means in terms of the answer being computed.

When To Use It

Use 1D DP when one index, amount, length, or position is enough to identify the subproblem.

Common signals include sequences, steps, amounts, prefixes, and decisions where the future depends only on one position or value.

The Main Point

1D DP fits when one variable identifies the subproblem. The table dimension comes from the state, not merely from the input being a list.