dynamic-programming

Dynamic Programming

Overview

Dynamic programming is not "try every recurrence and cache it." DP teaches a discipline: prove the subproblems are independent, choose state variables that preserve all information needed for future choices, compute each distinct subproblem once, and store enough choice information to reconstruct the requested solution.

Core principle: before writing a table, identify the choice, prove optimal substructure by cut-and-paste, verify overlapping subproblems, then decide whether the answer needs only values or also reconstruction metadata.

Shared CLRS Conventions

Follow the parent clrs skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide proof style. Keep recurrences, bounds, thresholds, and probability sums in display LaTeX blocks rather than inline prose.

Output Discipline for DP Answers

When a prompt asks for a DP answer, start with the answer itself. Do not mention reading skill files, planning the response, recalling the chapter, checking requirements, or applying this skill. Those sentences are scratch-work and violate the parent clrs skill. If a task requires reading files first, do it silently; the delivered answer must not say that it happened.

Use prose for names such as "the value table" or "the split table," then put formal notation in a display block. Do not put table entries, index inequalities, dimensions, recurrences, bounds, matrix names, prefix names, key names, or probability symbols in inline math or inline code spans. For DP answers, inline mathematical notation is not "small enough" to be safe. If a sentence needs notation, split it into a prose sentence followed by a display block.

Forbidden answer fragments:

• "Let $m[i,j]$ denote..."
• "where $1\le i\le j\le n$"
• "matrix $A_i$ has dimensions $p_{i-1}\times p_i$"
• "If $x_i=y_j$, use..."
• "store root[i,j]"

Correct pattern:

Let the value table store the minimum scalar multiplication cost for the interval below.

$$
A_i\cdots A_j
$$

The legal indices are below.

$$
1\le i\le j\le n
$$

The split position must be in the range below.

$$
i\le k<j
$$

The running time is below.

$$
\Theta(n^3)
$$

The value and split tables use the space below.

$$
\Theta(n^2)
$$