13.1 DP State Design

State design is the most important step in dynamic programming. Once the state is correct, the recurrence relation often becomes obvious. When the state is poorly designed, every subsequent step becomes difficult: transitions become complicated, memory usage grows unnecessarily, correctness proofs become fragile, and optimization opportunities disappear.

Many beginners focus immediately on finding recurrence relations. Experienced algorithm designers spend most of their effort defining the state itself. A well-designed state captures exactly the information required to solve a subproblem and nothing more.

Problem

Given a problem that exhibits overlapping subproblems and optimal substructure, how do we design a dynamic programming state that leads to an efficient and correct solution?

Understanding What a State Represents

A dynamic programming state represents a subproblem.

For example, consider computing Fibonacci numbers:

$$ F(n)=F(n-1)+F(n-2) $$

A natural state is:

$$ dp[i] $$

where:

dp[i] = the value of the ith Fibonacci number.

Each state corresponds to a smaller version of the original problem.

The key observation is that a state should answer a meaningful question.

Bad state:

dp[i] = something related to i

Good state:

dp[i] = number of ways to reach position i

The state description should be understandable without reading the recurrence.

Recipe 1: Define the Final Answer First

Before creating any state, identify the final answer.

Suppose we want the minimum cost path from the top-left corner of a grid to cell (n,m).

The final answer might be:

minimum cost to reach (n,m)

This immediately suggests:

dp[i][j]

where:

dp[i][j] = minimum cost to reach cell (i,j)

Working backward from the final answer frequently reveals the correct state.

Recipe 2: Describe a Subproblem

Every state should correspond to a smaller problem of the same type.

Consider the staircase problem.

Given:

You may climb 1 or 2 steps.
How many ways can you reach step n?

Natural state:

dp[i]

Meaning:

number of ways to reach step i

Now every state asks the same question as the original problem, just for a smaller staircase.

This self-similarity is one of the strongest indicators that the state is correct.

Recipe 3: Store Only Necessary Information

Consider finding the longest increasing subsequence.

A naive attempt might store:

entire sequence used so far

This creates an enormous state space.

Instead we observe that only a few facts affect future decisions.

One useful state is:

dp[i]

meaning:

length of the longest increasing subsequence ending at position i

The actual sequence is unnecessary during optimization.

A useful rule:

Store information required for future decisions, not information that merely explains the past.

Example: Coin Change

Problem:

Given coin values, find the minimum number of coins needed to make amount n.

Final answer:

minimum coins for amount n

Natural state:

dp[x]

where:

dp[x] = minimum number of coins needed to form amount x

The state contains only:

current amount

Nothing else influences future decisions.

This produces a compact state space of size:

$$ O(n) $$

Example: Grid Paths

Problem:

Count paths from (0,0) to (n,m).
Move only right or down.

Natural state:

dp[i][j]

Meaning:

number of paths to cell (i,j)

The state captures:

row
column

No additional information is needed.

State count:

$$ O(nm) $$

Example: Knapsack

Problem:

Select items with maximum value.
Total weight ≤ W.

A common state is:

dp[i][w]

Meaning:

maximum value obtainable
using first i items
with capacity w

Two facts determine future possibilities:

current item index
remaining capacity

Removing either makes the problem impossible to solve.

Adding extra information usually wastes memory.

State Dimensions

Every state variable creates a dimension.

Examples:

State	Dimensions
`dp[i]`	1
`dp[i][j]`	2
`dp[i][j][k]`	3
`dp[i][j][k][m]`	4

Complexity grows rapidly.

If:

n = 100

Then:

Dimensions	States
1	100
2	10,000
3	1,000,000
4	100,000,000

This phenomenon is called the curse of dimensionality.

One of the most important optimization techniques in dynamic programming is reducing the number of state dimensions.

Example: Longest Common Subsequence

Given strings:

A
B

Natural state:

dp[i][j]

Meaning:

length of the LCS
between A[0...i]
and B[0...j]

Each dimension corresponds to progress within one string.

The state space size becomes:

$$ O(nm) $$

which is manageable.

Attempting to store the actual subsequence would dramatically increase complexity.

State Compression Thinking

Suppose a state is:

dp[i][j][k]

Ask:

Can one variable be derived from the others?

If yes:

remove it

Example:

current row
current column
steps taken

Sometimes:

$$ steps = row + column $$

The third dimension becomes redundant.

The state shrinks from:

$$ O(n^3) $$

to:

$$ O(n^2) $$

A small observation can produce enormous performance gains.

Common State Patterns

Prefix States

dp[i]

Represents:

solution using first i elements

Examples:

Fibonacci
Staircase
Coin change

Position States

dp[i][j]

Represents:

state at coordinate (i,j)

Examples:

Grid paths
Shortest path in matrix

Interval States

dp[l][r]

Represents:

solution inside interval [l,r]

Examples:

Matrix chain multiplication
Interval merging

Subset States

dp[mask]

Represents:

solution for a subset

Examples:

Traveling salesman
Set cover variants

Tree States

dp[node]

Represents:

solution for subtree rooted at node

Examples:

Tree diameter
Maximum independent set on trees

State Design Checklist

Before implementing a recurrence, verify:

Does the state describe a well-defined subproblem?
Can every state be computed from smaller states?
Does the state contain only necessary information?
Can any dimension be removed?
Is the total number of states manageable?
Can the final answer be extracted directly?

If any answer is "no", redesign the state before proceeding.

Complexity Analysis

If a state has:

$$ S $$

possible values and each transition costs:

$$ T $$

then total running time is approximately:

$$ O(S \times T) $$

Therefore state count often dominates overall complexity.

Many successful dynamic programming optimizations come from reducing:

$$ S $$

rather than improving transitions.

Takeaway

Dynamic programming begins with state design, not recurrence design. A state should represent a clear subproblem, contain only information required for future decisions, minimize dimensions whenever possible, and make the final answer easy to extract. Once a good state exists, recurrences, correctness proofs, and optimizations become significantly easier to derive.