13.5 One-Dimensional Dynamic Programming

One-dimensional dynamic programming is the simplest and most common form of dynamic programming. The state is represented by a single index, and each state typically depends on a small number of earlier states. Many classical problems, including Fibonacci numbers, staircase counting, coin change, rod cutting, and longest increasing subsequence, begin with a one-dimensional formulation.

Mastering one-dimensional dynamic programming develops the core skills needed for all later dynamic programming techniques. State design, recurrence construction, initialization, iteration ordering, and space optimization all appear here in their simplest form.

Problem

How do we design and implement dynamic programming solutions where each state is identified by a single variable?

Understanding Linear State Spaces

A one-dimensional state usually looks like:

$$ dp[i] $$

The index often represents:

a position
a prefix length
an amount
a time step
a resource level

Examples:

dp[i] = best solution using first i elements

dp[i] = minimum cost to reach position i

dp[i] = number of ways to form amount i

dp[i] = longest subsequence ending at i

The key characteristic is that every state is described by one coordinate.

Example: Fibonacci Numbers

State:

$$ dp[i] $$

Meaning:

ith Fibonacci number

Recurrence:

$$ dp[i] = dp[i-1] + dp[i-2] $$

Initialization:

$$ dp[0]=0 $$

$$ dp[1]=1 $$

Implementation:

func fib(n int) int {
    if n <= 1 {
        return n
    }

    dp := make([]int, n+1)

    dp[0] = 0
    dp[1] = 1

    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }

    return dp[n]
}

This is the canonical one-dimensional DP.

Example: Staircase Counting

Problem:

You may climb 1 or 2 steps.
Count ways to reach step n.

State:

$$ dp[i] $$

Meaning:

number of ways to reach step i

Recurrence:

$$ dp[i] = dp[i-1] + dp[i-2] $$

Initialization:

$$ dp[0]=1 $$

$$ dp[1]=1 $$

The interpretation differs from Fibonacci, but the recurrence is identical.

This illustrates an important principle:

Different problems can share the same dynamic programming structure.

Example: Minimum Cost Climbing Stairs

Problem:

Each stair has a cost.
Minimize total cost.

State:

$$ dp[i] $$

Meaning:

minimum cost to reach stair i

Recurrence:

$$ dp[i] = cost[i] + \min(dp[i-1],dp[i-2]) $$

Implementation:

for i := 2; i < n; i++ {
    dp[i] =
        cost[i] +
        min(dp[i-1], dp[i-2])
}

This introduces minimization rather than counting.

Example: Coin Change

Problem:

Minimum number of coins
needed to form amount x

State:

$$ dp[x] $$

Meaning:

minimum coins for amount x

Recurrence:

$$ dp[x] = 1+ \min(dp[x-c]) $$

for all valid coin values (c).

Implementation:

for amount := 1; amount <= target; amount++ {
    for _, coin := range coins {

        if amount >= coin {
            dp[amount] = min(
                dp[amount],
                dp[amount-coin]+1,
            )
        }
    }
}

Unlike Fibonacci, each state may depend on many earlier states.

Example: Rod Cutting

Problem:

Cut rod of length n
for maximum profit

State:

$$ dp[i] $$

Meaning:

maximum revenue
for rod length i

For every possible first cut:

$$ dp[i] = \max ( price[j] + dp[i-j] ) $$

for:

$$ 1 \le j \le i $$

Implementation:

for length := 1; length <= n; length++ {

    for cut := 1; cut <= length; cut++ {

        dp[length] = max(
            dp[length],
            price[cut]+dp[length-cut],
        )
    }
}

This pattern appears frequently in optimization problems.

State Dependency Patterns

Most one-dimensional DPs fall into several common categories.

Fixed-Width Dependencies

Example:

$$ dp[i] = dp[i-1] + dp[i-2] $$

Dependencies are limited to a constant number of earlier states.

Examples:

Fibonacci
Staircase counting

Complexity:

$$ O(n) $$

Variable-Width Dependencies

Example:

$$ dp[i] = \min(dp[i-j]) $$

for many values of (j).

Examples:

Coin change
Word segmentation
Rod cutting

Complexity:

$$ O(n^2) $$

$$ O(nk) $$

depending on transition count.

Prefix Dynamic Programming

State:

$$ dp[i] $$

Meaning:

solution using first i elements

Examples:

Sequence optimization
String decomposition
Resource allocation

The state grows from left to right.

Position Dynamic Programming

State:

$$ dp[i] $$

Meaning:

best solution ending at position i

Examples:

Longest increasing subsequence
Maximum subarray
Path optimization

Each state focuses on a location rather than a prefix.

Example: Maximum Subarray Sum

Given:

array a

State:

$$ dp[i] $$

Meaning:

maximum subarray sum
ending at position i

Recurrence:

$$ dp[i] = \max ( a[i], dp[i-1]+a[i] ) $$

The choice:

start new subarray
extend previous subarray

Implementation:

dp[0] = a[0]

for i := 1; i < n; i++ {

    dp[i] = max(
        a[i],
        dp[i-1]+a[i],
    )
}

This is commonly known as Kadane's algorithm.

Example: Longest Increasing Subsequence

State:

$$ dp[i] $$

Meaning:

length of LIS ending at i

Recurrence:

$$ dp[i] = 1+ \max(dp[j]) $$

for:

$$ j<i $$

and

$$ a[j]<a[i] $$

Implementation:

for i := 0; i < n; i++ {

    dp[i] = 1

    for j := 0; j < i; j++ {

        if a[j] < a[i] {

            dp[i] = max(
                dp[i],
                dp[j]+1,
            )
        }
    }
}

This demonstrates a common (O(n^2)) transition pattern.

Space Optimization

Many one-dimensional DPs require only a few previous states.

Consider:

$$ dp[i] = dp[i-1] + dp[i-2] $$

Full table:

$$ O(n) $$

memory.

Optimized:

prev2 := 0
prev1 := 1

for i := 2; i <= n; i++ {

    current := prev1 + prev2

    prev2 = prev1
    prev1 = current
}

Memory becomes:

$$ O(1) $$

This optimization is possible whenever old states are never revisited.

Common Mistakes

Incorrect Initialization

Many recurrences rely heavily on base states.

Example:

dp[0]

often represents:

empty sequence
zero amount
starting position

Misinterpreting this state breaks the entire solution.

Wrong Iteration Direction

Suppose:

$$ dp[i] = dp[i+1] +1 $$

Then left-to-right iteration fails.

Dependencies must already exist before computation.

Mixing Meanings

Example:

dp[i]

sometimes interpreted as:

first i elements

and elsewhere as:

ending at position i

A state must maintain one consistent meaning.

Overflow

Counting problems often grow rapidly.

Use appropriate numeric types when state values become large.

Recognizing One-Dimensional DP

Several clues strongly suggest a one-dimensional formulation.

Single Variable Progress

Examples:

amount
position
length
time

Smaller Prefixes

Problems involving:

first i elements

often lead naturally to:

$$ dp[i] $$

Sequential Decisions

When decisions occur in a linear order, a one-dimensional state frequently suffices.

Complexity Analysis

Let:

$$ n $$

be the number of states.

If each state examines:

$$ k $$

transitions:

$$ O(nk) $$

If:

$$ k=O(1) $$

then:

$$ O(n) $$

running time.

Memory:

$$ O(n) $$

before optimization.

Many one-dimensional DPs can be reduced to:

$$ O(1) $$

$$ O(k) $$

memory.

Takeaway

One-dimensional dynamic programming organizes subproblems along a single axis such as position, amount, length, or time. Despite its apparent simplicity, this model captures a wide variety of important problems, including optimization, counting, feasibility, and sequence analysis. Understanding how to design states, derive transitions, initialize base cases, and optimize memory in one-dimensional dynamic programming provides the foundation for all higher-dimensional dynamic programming techniques that follow.