13.2 Recurrence Relations

After defining a state, the next step is to determine how one state depends on other states. This dependency is called a recurrence relation. The recurrence is the mathematical heart of a dynamic programming solution. It describes how larger subproblems can be constructed from smaller subproblems that have already been solved.

A correctly designed state without a recurrence is useless. A recurrence without a correct state is usually impossible to derive. Dynamic programming succeeds when these two components fit together naturally.

Problem

Given a valid dynamic programming state, how do we derive a recurrence relation that computes every state correctly and efficiently?

Understanding Recurrences

A recurrence expresses a state in terms of smaller states.

Consider Fibonacci numbers:

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

The corresponding dynamic programming state is:

dp[i] = ith Fibonacci number

The recurrence becomes:

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

The state defines what is stored.

The recurrence defines how it is computed.

Recipe 1: Identify the Last Decision

Many recurrences can be derived by asking:

What was the last action performed before reaching this state?

Consider the staircase problem.

Problem:

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

State:

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

To reach step i, the last move must be:

• from step i-1
• from step i-2

Therefore:

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

The recurrence follows directly from analyzing the final decision.

Recipe 2: Partition the Solution Space

Sometimes a state can be reached through multiple mutually exclusive possibilities.

Consider coin change counting.

Problem:

Count the number of ways
to make amount x.

State:

dp[x]

For each coin value:

coin

we can arrive at:

x

from:

x - coin

This yields:

$$ dp[x]=\sum dp[x-coin] $$

The recurrence partitions all valid solutions according to their final coin.

Example: Minimum Coin Change

Problem:

Minimum number of coins
to form amount x

State:

dp[x]

Suppose coin values are:

1, 3, 4

The final coin could be any available denomination.

Thus:

$$ dp[x] = 1+\min (dp[x-1],dp[x-3],dp[x-4]) $$

Every candidate solution corresponds to choosing one final coin.

The recurrence chooses the best among them.

Recipe 3: Define the Transition Precisely

A transition transforms one state into another.

Consider a grid path problem.

State:

dp[i][j]
=
number of paths to cell (i,j)

Allowed moves:

• right
• down

To reach cell (i,j):

• come from above
• come from left

Therefore:

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

The transition is:

above -> current
left -> current

Every recurrence is built from such transitions.

Example: Longest Increasing Subsequence

Given:

a[0...n-1]

State:

dp[i]
=
length of longest increasing subsequence
ending at position i

Which previous positions can precede i?

Any position:

j < i

where:

a[j] < a[i]

Thus:

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

for all valid predecessors.

This recurrence emerges naturally from the state definition.

Example: Knapsack

Problem:

Maximum value
capacity W

State:

dp[i][w]

Meaning:

first i items
capacity w

For item i:

Two possibilities exist.

Skip the Item

Value becomes:

$$ dp[i-1][w] $$

Take the Item

Value becomes:

$$ dp[i-1][w-weight_i] + value_i $$

Choose the better option:

$$ dp[i][w] = \max ( dp[i-1][w], dp[i-1][w-weight_i]+value_i ) $$

Many dynamic programming recurrences are simply exhaustive comparisons of all valid decisions.

Correctness Through Exhaustiveness

A recurrence must cover every possible valid solution.

Suppose a recurrence ignores one possible transition.

Then some optimal solution may never be considered.

The algorithm becomes incorrect.

A useful verification method is:

Take any valid solution.
Can it be generated by the recurrence?

If the answer is no, the recurrence is incomplete.

Correctness Through Exclusivity

A recurrence must avoid counting the same solution multiple times unless duplication is intended.

Consider counting paths.

If two transitions represent the same path construction process, overcounting occurs.

Many counting DP bugs originate from overlapping transitions.

Always verify:

Do two transitions generate identical solutions?

If yes, redesign the recurrence.

Min, Max, Count, and Boolean Recurrences

Most dynamic programming recurrences belong to four categories.

Minimum

minimum cost

Pattern:

$$ dp[state] = \min(...) $$

Examples:

• shortest path
• coin change
• edit distance

Maximum

maximum profit

Pattern:

$$ dp[state] = \max(...) $$

Examples:

• knapsack
• LIS
• scheduling

Counting

number of solutions

Pattern:

$$ dp[state] = \sum(...) $$

Examples:

• path counting
• partitions
• combinatorics

Feasibility

possible or impossible

Pattern:

$$ dp[state] = OR(...) $$

Examples:

• subset sum
• reachability
• game states

Recognizing the category often reveals the recurrence immediately.

Visualizing Dependencies

Consider:

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

Dependency graph:

i
|
+-- i-1
|
+-- i-2

For:

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

Dependency graph:

(i,j)

  ^
  |
(i-1,j)

(i,j-1) ->

Drawing dependency graphs helps determine computation order later.

Common Mistakes

Missing Cases

Example:

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

when transition from i-2 also exists.

Incomplete recurrence.

Invalid States

Example:

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

for:

i < 10

Produces illegal accesses.

Boundary conditions must be handled.

Double Counting

Two transitions generate identical solutions.

Counts become larger than expected.

Circular Dependencies

Example:

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

State depends on a future state.

Tabulation becomes impossible.

Deriving Recurrences Systematically

For every state:

1. Define precisely what the state means.

2. Consider the final decision.

3. Enumerate all valid previous states.

4. Determine how each previous state contributes.

5. Combine contributions using:

   • minimum
   • maximum
   • addition
   • logical operations

6. Verify completeness.

7. Verify no double counting.

This process works for most dynamic programming problems.

Complexity Analysis

Suppose:

S states

and each state examines:

K transitions

Then total complexity is:

$$ O(S \times K) $$

State design determines:

$$ S $$

Recurrence design determines:

$$ K $$

Many advanced optimizations focus on reducing transition costs while preserving the same state space.

Takeaway

A recurrence relation defines how each dynamic programming state is computed from smaller states. The most reliable approach is to analyze the final decision, enumerate all valid predecessors, and combine their contributions according to the problem objective. A correct recurrence must cover every valid solution, avoid double counting, respect dependency ordering, and provide a clear path from base cases to the final answer.