DYNAMIC PROGRAMMING › PATTERNS

DP on 1D Arrays

This pattern uses a one-dimensional DP array to track answers for prefixes, positions, or counts in linear problems.

Time

O(N)

Space

O(N)

Key Principle 1

Common examples include Fibonacci, climbing stairs, house robber, and subset sum.

Key Principle 2

The index usually represents how much of the input has been processed.

Key Principle 3

Some solutions scan left-to-right, while others need a reverse pass to avoid reuse.

Key Principle 4

Many 1D DP solutions can be compressed to O(1) space after the recurrence is clear.

Loading Lab...

Dp On 1d Arrays