Dynamic programming: Definition & Examples

Dynamic programming (DP) is a method for solving a problem through smaller subproblems, storing their answers so that repeated subproblems are reused. In optimisation, each stored answer is the best value attainable from a precisely defined state. For a quant, the hard part is often choosing a state that retains every fact needed for future decisions; a fast table cannot repair an incomplete model.

DP also solves counting and feasibility problems. It does not require writing a recursive function: memoisation and bottom-up table filling are two ways to organise the same dependencies.

A six-unit decision that defeats a local rule

Consider a fictional chunking task. Complete exactly 6 units using chunks of 1, 3 or 4 units, with unlimited reuse of each size. Each chunk costs one operation, regardless of its size. Minimise the number of operations. Order has no effect, and there are no timing, liquidity or market-impact constraints.

A greedy algorithm that repeatedly takes the largest size that fits chooses

4+1+1

: three operations. But

3+3

needs only two. The first locally attractive choice can leave an expensive remainder.

Let

C(q)

be the minimum number of chunks needed to complete exactly $q$ remaining units. The permitted sizes form

S=\{1,3,4\}

. Then

C(0)=0,\qquad C(q)=\min_{\substack{s\in S\s\le q}}\{1+C(q-s)\},\quad q>0.

A candidate is feasible only if its remainder is feasible. Set an unreachable state's value to $+\infty$ , and define the minimum over no candidates as $+\infty$ . Here the 1-unit chunk makes every nonnegative integer target reachable. With sizes $\{3,4\}$ instead, target 2 would be unreachable; returning zero would incorrectly label failure as a free solution.

Because every allowed size is positive, $q-s<q$ . Fill the table from 0 upward, so each needed remainder already has an answer.

For chunk sizes 1, 3 and 4 units, states q from 0 through 6 have minimum counts 0, 1, 2, 1, 1, 2 and 2. At q equals 6, first chunks 1, 3 and 4 produce total counts 3, 2 and 3. Recording size 3 reconstructs 6 to 3 to 0, giving 3 plus 3. Greedy gives 4 plus 1 plus 1.

Each cell solves an exact remaining-quantity problem. At 6 units, comparing all feasible first choices selects 3 units; saved choices recover the two-chunk plan. Fictional operation counts, not trading costs.

At the target,

C(6)=1+\min\{C(5),C(3),C(2)\} =1+\min\{2,1,2\}=2.

Why keeping only the best remainder works

Suppose an optimal plan starts with a chunk of size

s

. Its remaining chunks must solve the

q-s

problem optimally. Otherwise, replace them with a better plan for that same remainder: the first chunk still fits, the total is still

q

, and the operation count falls, contradicting optimality. This replacement argument is the principle of optimality for this model.

It holds because the remaining quantity fully determines the future problem: sizes remain available, past choices create no extra restrictions, and operation counts add. Different paths can reach the same remainder, which creates the overlap that makes reusing $C(q)$ useful.

If each size could be used only once, remaining quantity alone would lose information: the available sizes would also matter. If costs depended on time or inventory history, the state and recurrence would need to retain the relevant information. The toy optimum proves nothing about real optimal execution, where impact, uncertainty and constraints change the problem.

Save decisions as well as values

The value $C(6)=2$ says how good the answer is. To recover a plan, store a size attaining the minimum at each reachable state, then repeatedly subtract it. This bottom-up Python example assumes a nonnegative integer target and a nonempty tuple of positive integer sizes.

def min_chunks(target: int, sizes: tuple[int, ...]) -> tuple[int | None, list[int]]:
    """Return the minimum count and one exact plan, or (None, [])."""
    cost = [float("inf")] * (target + 1)
    choice = [None] * (target + 1)
    cost[0] = 0
    for q in range(1, target + 1):
        for size in sizes:
            if size <= q and 1 + cost[q - size] < cost[q]:
                cost[q] = 1 + cost[q - size]
                choice[q] = size
    if cost[target] == float("inf"):
        return None, []
    plan = []
    q = target
    while q > 0:
        size = choice[q]
        plan.append(size)
        q -= size
    return int(cost[target]), plan

print(min_chunks(6, (1, 3, 4)))
# (2, [3, 3])
print(min_chunks(2, (3, 4)))
# (None, [])
print(min_chunks(0, (1, 3, 4)))
# (0, [])

The strict improvement test keeps the first encountered size when candidates tie; another tie rule may return a different equally good plan. Reconstruction terminates because every recorded size is positive.

For target

Q

and

k

permitted sizes, this table tests

Qk

size candidates and stores

O(Q)

entries. Under constant-time arithmetic and indexing, its running time is

O(Qk)

, including reconstruction. This is pseudopolynomial in a binary-encoded target: increasing the number of bits used to describe

Q

can increase the table far more than linearly. More state variables can also make the table impractically large.

A top-down version follows the recurrence through recursion, caching each state when first computed. Python's functools.cache provides an unbounded memoisation wrapper; the cache must belong to the particular problem inputs. Reusing results after changing the permitted sizes would answer a different problem.

Continue with the full design recipe

Dynamic Programming: The SRBOT Recipe develops subproblems, recurrences, base cases and evaluation order through rod cutting, then compares memoised recursion with tables. The public page is a preview; the full lesson requires membership.

Sources

MIT 6.006, Lecture 15: Recursive Algorithms, pp. 3–4: reusing subproblem solutions, evaluation order, reconstruction and time analysis. The chunking example and replacement argument above are original to this article.
Python 3.14 documentation: functools.cache and lru_cache: cache semantics and the memoised Fibonacci example. Documentation read as version 3.14.10; article code checked with Python 3.14.4.

A six-unit decision that defeats a local rule

Why keeping only the best remainder works

Save decisions as well as values

Continue with the full design recipe

Sources

Related terms

Greedy algorithm

Memoisation

Recursion