13.20 Dynamic Programming Design Patterns and Problem-Solving Framework

Throughout this chapter, we have studied many different forms of dynamic programming:

one-dimensional DP
two-dimensional DP
knapsack DP
longest common subsequence
longest increasing subsequence
edit distance
interval DP
tree DP
bitmask DP
probability DP
counting DP
optimization DP
convex hull trick
divide-and-conquer optimization
Knuth optimization

At first glance, these techniques may appear unrelated. In practice, experienced programmers approach them using the same underlying process.

The difference between beginners and experts is rarely knowledge of more recurrences. Experts recognize patterns quickly and systematically transform a problem into states, transitions, and base cases.

This final section presents a practical framework for designing dynamic programming solutions.

Problem

How do we recognize dynamic programming opportunities and systematically derive correct solutions?

Step 1: Identify the Subproblem

Every dynamic programming solution begins with a question:

What smaller version of the problem should be solved?

For example:

first i elements

first i and j characters

interval [l,r]

subtree rooted at node u

subset represented by mask

The subproblem should resemble the original problem as closely as possible.

Good subproblems allow recursion to emerge naturally.

Bad subproblems create awkward transitions.

Example: Fibonacci

Question:

What is Fibonacci(n)?

Smaller versions:

Fibonacci(n-1)

Fibonacci(n-2)

State:

$$ dp[i] $$

The state follows directly from the smaller problem definition.

Step 2: Define the State Precisely

The state is the most important part of a dynamic programming solution.

A state must contain all information required for future decisions.

Nothing more.

Nothing less.

Examples:

Coin Change

$$ dp[x] $$

Meaning:

minimum coins
needed for amount x

LCS

$$ dp[i][j] $$

Meaning:

LCS length
between first i characters
and first j characters

Knapsack

$$ dp[i][w] $$

Meaning:

maximum value
using first i items
with capacity w

Write the state meaning in plain English before writing any recurrence.

This simple habit prevents many mistakes.

Step 3: Determine the Final Decision

Most recurrences arise from examining the last decision.

Ask:

What must happen immediately before this state is reached?

Examples:

Staircase

Final move:

1 step

or

2 steps

Edit Distance

Final operation:

insert

delete

replace

match

Interval DP

Final action:

choose split point k

Tree DP

Final action:

combine child solutions

The recurrence often emerges directly from this question.

Step 4: Derive the Transition

Once the final decision is known, express the state in terms of smaller states.

Examples:

Fibonacci

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

Coin Change

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

LCS

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

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

Knapsack

$$ dp[i][w] = \max ( skip, take ) $$

Transitions are the mathematical expression of decisions.

Step 5: Determine Base Cases

Base cases terminate recursion.

Ask:

What are the smallest possible subproblems?

Examples:

Fibonacci

$$ dp[0]=0 $$

$$ dp[1]=1 $$

LCS

$$ dp[0][j]=0 $$

$$ dp[i][0]=0 $$

Edit Distance

$$ dp[0][j]=j $$

$$ dp[i][0]=i $$

Many incorrect solutions have correct transitions but incorrect base cases.

Step 6: Choose Computation Order

Dependencies determine evaluation order.

Examples:

One-Dimensional DP

left to right

Interval DP

short intervals
to long intervals

Tree DP

children before parent

DAG DP

topological order

A useful rule:

Compute dependencies before dependents.

Everything else follows from this principle.

Step 7: Verify State Coverage

Ask:

Does every valid solution correspond to a state path?

and:

Does every state path correspond to a valid solution?

This prevents:

missing solutions
invalid solutions
double counting

Verification is often more important than implementation.

Common Dynamic Programming Patterns

Most problems fit a small number of recurring templates.

Pattern 1: Linear Progression

State:

$$ dp[i] $$

Examples:

Fibonacci
staircase
coin change
house robber

Clue:

position

length

amount

time

Pattern 2: Sequence Comparison

State:

$$ dp[i][j] $$

Examples:

LCS
edit distance
sequence alignment

Clue:

two strings

two sequences

Pattern 3: Resource Allocation

State:

$$ dp[i][capacity] $$

Examples:

knapsack
scheduling
budgeting

Clue:

resource constraint

Pattern 4: Interval Optimization

State:

$$ dp[l][r] $$

Examples:

matrix chain multiplication
file merging
burst balloons

Clue:

split interval

Pattern 5: Tree Aggregation

State:

$$ dp[node] $$

or:

$$ dp[node][state] $$

Examples:

subtree calculations
independent set
tree diameter

Clue:

hierarchical structure

Pattern 6: Subset Selection

State:

$$ dp[mask] $$

or:

$$ dp[mask][i] $$

Examples:

TSP
assignment
Hamiltonian path

Clue:

small set
of choices

Pattern 7: Counting

State:

number of ways

Transition:

addition

Clue:

how many?

Pattern 8: Optimization

State:

best value

Transition:

min

or

max

Clue:

best

largest

smallest

Top-Down Versus Bottom-Up

Every dynamic programming solution can be expressed in two forms.

Top-Down

Use recursion and memoization.

func solve(state) {

    if memoized {
        return value
    }

    compute value

    return value
}

Advantages:

natural derivation
easy implementation

Disadvantages:

recursion overhead
stack limitations

Bottom-Up

Build states iteratively.

Advantages:

predictable performance
easier optimization

Disadvantages:

requires explicit ordering

Both approaches compute the same states.

Space Optimization Checklist

After obtaining a correct solution, ask:

Are Older States Needed?

Example:

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

Only two values are needed.

Are Entire Rows Needed?

Example:

$$ dp[i][j] $$

depends only on:

previous row

Use rolling arrays.

Can State Dimensions Be Removed?

Example:

current item index

may be derivable from:

number of selected elements

Removing dimensions often produces the largest gains.

Debugging Dynamic Programming

When a solution fails:

Verify State Meaning

Many bugs originate from ambiguous states.

Check Base Cases

Most incorrect tables fail immediately near boundaries.

Trace Small Inputs

Compute:

n = 1

n = 2

n = 3

by hand.

Print DP Tables

Visual inspection often reveals incorrect transitions.

Compare with Brute Force

For small inputs:

generate all solutions

compare answers

This technique catches subtle errors quickly.

Recognizing Dynamic Programming

Strong indicators include:

optimal value

number of ways

overlapping subproblems

repeated calculations

small state space

recursive structure

Ask:

If I solve a smaller version of this problem, can it help solve a larger version?

If the answer is yes, dynamic programming may be applicable.

Dynamic Programming Versus Other Techniques

Not every optimization problem requires dynamic programming.

Technique	Typical Clue
Greedy	local choice always optimal
Divide and Conquer	independent subproblems
Dynamic Programming	overlapping subproblems
Backtracking	exhaustive search
Graph Algorithms	path or connectivity structure
Binary Search	monotonic answer space

Choosing the correct paradigm is often more important than implementation details.

A Dynamic Programming Checklist

Before coding, answer these questions:

What is the state?
What does the state mean?
What is the final answer state?
What decisions lead into the state?
What is the recurrence?
What are the base cases?
What computation order satisfies dependencies?
Can memory be reduced?
Can transitions be optimized?
How can correctness be verified?

If all ten questions have clear answers, implementation is usually straightforward.

Takeaway

Dynamic programming is not a collection of isolated tricks but a systematic method for solving problems with overlapping subproblems and optimal substructure. Whether the state represents a position, a pair of strings, an interval, a subtree, or a subset, the design process remains remarkably consistent: define the subproblem, identify the final decision, derive the recurrence, establish base cases, and compute states in dependency order. Mastering these patterns allows you to move beyond memorizing individual algorithms and begin designing dynamic programming solutions for entirely new problems. This ability is the true goal of studying dynamic programming.