13.16 Optimization Dynamic Programming

Optimization dynamic programming is the form most programmers first associate with DP. The goal is not to count solutions or compute probabilities, but to find the best possible value among many choices.

The word "best" depends on the problem. It may mean minimum cost, maximum profit, shortest time, largest score, fewest edits, lowest risk, or greatest utility. The structure, however, is the same: each state records the optimal value for a subproblem, and each transition represents a legal decision.

This section consolidates the optimization pattern that has appeared throughout the chapter. Knapsack maximizes value. Edit distance minimizes operations. Matrix chain multiplication minimizes cost. Longest increasing subsequence maximizes length. These are different problems, but they share the same design method.

Problem

How do we design dynamic programming algorithms that choose the best solution among many valid alternatives?

The Optimization Pattern

A typical optimization state looks like:

$$ dp[state] $$

Meaning:

The best value achievable for this subproblem.

The recurrence usually has the form:

$$ dp[state] = \min_{choice} cost(choice) $$

or:

$$ dp[state] = \max_{choice} value(choice) $$

The state defines the subproblem.

The transition defines the choice.

The aggregation operator defines the objective.

Example: Minimum Coin Change

Given coin values:

1, 3, 4

Find the minimum number of coins needed to form amount x.

State:

$$ dp[x] $$

Meaning:

minimum number of coins
needed to form amount x

Transition:

choose the last coin

Recurrence:

$$ dp[x] = 1+ \min_{coin} dp[x-coin] $$

where:

$$ x-coin \ge 0 $$

Base case:

$$ dp[0]=0 $$

This is a minimization DP.

Implementation

func MinCoins(coins []int, target int) int {

    const inf = int(1e9)

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

    for x := 1; x <= target; x++ {
        dp[x] = inf
    }

    dp[0] = 0

    for x := 1; x <= target; x++ {

        for _, coin := range coins {

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

    if dp[target] == inf {
        return -1
    }

    return dp[target]
}

The sentinel value inf represents an unreachable state.

Min Versus Max

Optimization DP comes in two common forms.

Minimization

Use when the objective asks for:

least cost

fewest steps

shortest distance

minimum penalty

Typical initialization:

infinity

Transition:

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

Maximization

Use when the objective asks for:

largest profit

maximum score

longest sequence

greatest reward

Typical initialization:

negative infinity

Transition:

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

Using the wrong default value is a common source of silent errors.

Example: Maximum Value Path

Given a grid of values, move only right or down. Find the maximum value collected from the top-left cell to the bottom-right cell.

State:

$$ dp[i][j] $$

Meaning:

maximum value collected
when reaching cell (i,j)

Recurrence:

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

The same grid structure used for path counting now becomes an optimization problem.

Only the aggregation changes.

Example: House Robber

Given a line of houses, each containing money, choose houses so that no two adjacent houses are selected.

State:

$$ dp[i] $$

Meaning:

maximum money obtainable
from the first i houses

At house (i), two choices exist.

Skip it:

$$ dp[i-1] $$

Take it:

$$ dp[i-2]+value[i] $$

Recurrence:

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

This is the same include/exclude pattern used in knapsack and tree independent set.

Local Choice, Global Value

Optimization DP works because local choices are evaluated through already optimized subproblems.

For a transition:

$$ choice + dp[subproblem] $$

the subproblem value already assumes the best continuation.

This avoids enumerating complete solutions.

The recurrence considers only the immediate decision and delegates the rest to the DP table.

Optimal Substructure

Optimization DP requires optimal substructure.

A problem has optimal substructure when an optimal solution contains optimal solutions to its subproblems.

For example, if the cheapest path to cell (i,j) comes from (i-1,j), then the path to (i-1,j) must also be cheapest. If it were not, replacing it with a cheaper path would improve the final solution.

This property is what makes dynamic programming valid.

Overlapping Subproblems

Optimization alone is not enough.

Dynamic programming is useful when the same subproblems appear repeatedly.

If every subproblem is unique, recursion may still be correct, but memoization provides little benefit.

Good DP candidates usually have both:

optimal substructure

overlapping subproblems

The first gives correctness.

The second gives efficiency.

Choice Enumeration

Many optimization recurrences follow this structure:

best := initialValue

for _, choice := range choices {

    if valid(choice) {

        candidate :=
            transitionCost(choice) +
            dp[nextState(choice)]

        best = better(best, candidate)
    }
}

dp[state] = best

This template appears in coin change, knapsack, interval DP, shortest paths on DAGs, scheduling, and many game problems.

Reconstructing the Optimum

The DP table stores the optimal value.

To recover the actual decision sequence, store which choice produced that value.

Example:

parent[state] = choice

or:

take[i][w] = true

During reconstruction, follow recorded choices backward from the final state.

Without this auxiliary information, you may know the value but not the solution.

Tie Handling

Sometimes several choices produce the same optimal value.

Examples:

multiple shortest paths

multiple optimal knapsack selections

multiple longest subsequences

Tie handling should be deliberate.

You may choose:

first solution

lexicographically smallest solution

fewest items

stable reconstruction order

The DP value alone does not specify which optimal solution to return.

Sentinel Values

Optimization DP often needs sentinel values for impossible states.

For minimization:

const inf = int(1e9)

For maximization:

const negInf = -int(1e9)

Be careful when adding to sentinels.

This is unsafe:

candidate := dp[x] + cost

if:

dp[x] == inf

Guard impossible states explicitly when overflow is possible.

Example: Weighted Interval Scheduling

Given jobs with:

start time

end time

profit

Select non-overlapping jobs with maximum total profit.

After sorting by end time, define:

$$ dp[i] $$

as:

maximum profit using first i jobs

For job (i):

Skip it:

$$ dp[i-1] $$

Take it:

$$ profit_i + dp[p(i)] $$

where (p(i)) is the last job that ends before job (i) starts.

Recurrence:

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

This is a production-grade example of optimization DP.

The only extra work is computing (p(i)), usually with binary search.

Optimization DP and Shortest Paths

Shortest paths in a DAG can be interpreted as optimization DP.

State:

$$ dp[u] $$

Meaning:

shortest distance
from source to node u

Transition:

$$ dp[v] = \min ( dp[v], dp[u]+weight(u,v) ) $$

processed in topological order.

This viewpoint helps connect dynamic programming with graph algorithms.

Dijkstra and Bellman-Ford generalize similar relaxation ideas to broader graph classes.

Common Mistakes

Using Greedy Choice Without Proof

Optimization DP often solves problems where greedy fails.

Do not replace DP with a local heuristic unless an exchange argument or matroid property proves correctness.

Losing Necessary State

If future decisions depend on information not stored in the state, the recurrence may appear plausible but produce incorrect answers.

Bad Initialization

Minimization requires large initial values.

Maximization often requires small initial values.

Base cases must reflect the state definition.

Failing to Reconstruct

A DP table gives the optimal value.

It does not automatically give the selected objects, path, or sequence.

Overflow with Sentinels

Adding costs to inf or negInf can corrupt results.

Guard impossible states.

Complexity Analysis

Let:

$$ S $$

be the number of states.

Let:

$$ K $$

be the number of choices per state.

Then:

$$ O(SK) $$

time is typical.

Memory is:

$$ O(S) $$

unless reconstruction, multiple layers, or full tables are required.

The usual optimization levers are:

reduce state count

reduce choices per state

compress memory

precompute transition helpers

Recognizing Optimization DP

Strong indicators include:

minimum

maximum

best

least

fewest

largest

optimal

choose among alternatives

cost or profit

If the problem also has overlapping subproblems and a reusable state definition, dynamic programming is a strong candidate.

Takeaway

Optimization dynamic programming stores the best achievable value for each subproblem and derives larger solutions by enumerating valid choices. The recurrence uses min or max, base cases describe trivial subproblems, and sentinel values represent unreachable states. This pattern unifies many classic algorithms, including coin change, knapsack, edit distance, weighted scheduling, grid path optimization, and shortest paths on DAGs. Once the state is correct, the main design task is to enumerate all legal choices without omission, duplication, or unnecessary state.