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].
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.
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.
When To Use It
Use 1D DP when one index, amount, length, or position is enough to identify the subproblem.