1. The Implicit State-Space DAG & The SRTBOT Design Framework
Every Dynamic Programming problem reduces to evaluating a function on the vertices $V$ of an implicit Directed Acyclic Graph (DAG) $G = (V, E)$, where a directed edge $u \to v$ means computing state $v$ depends on the value of state $u$. MIT's 6.006 SRTBOT Framework turns DP design into a mechanical 6-step checklist:
- S — Subproblem Definition: Define the exact meaning of state $x \in V$ in plain English (often prefixes $A[0..i]$, suffixes $A[i..n]$, or substrings $A[i..j]$) and count $|V|$.
- R — Relate (Recurrence): Guess the last local decision among out-neighbors (or in-neighbors) of $x$ and express $dp[x] = \bigoplus_{u \to x} (dp[u] \otimes w(u, x))$ over a semiring $(\min, +)$, $(\max, +)$, or $(+, \times)$.
- T — Topological Order: Prove that the dependency graph $G$ is acyclic and specify an evaluation loop order (or DFS post-order) where every $u$ is finalized before $x$.
- B — Base Cases: Explicitly initialize source vertices in $G$ (in-degree $0$).
- O — Original Problem: Express the final answer as a single sink state $dp[t]$ or an aggregation over a subset of states.
- T — Time & Space Analysis: $\text{Time} = \sum_{x \in V} \text{work}(x) = O(|V| + |E|)$.
Core Invariant — Bellman's Principle of Optimality & Acyclicity
A problem exhibits Optimal Substructure if an optimal solution to state $x$ can be constructed strictly from optimal solutions to its predecessor subproblems $u \in N^-(x)$, paired with a Markovian (memoryless) state definition: how we arrived at state $u$ does not restrict which future transitions are legal from $u$. If how you reached $u$ matters (e.g., Longest Simple Path in a graph with cycles, which is NP-hard), then $u$ is missing state dimensions!
2. Pull DP ("Gather") vs. Push DP ("Scatter") & Parent Pointers
Given a topological ordering of states $u_1, u_2, \dots, u_{|V|}$, there are two dual ways to execute the relaxations:
- Pull DP (In-Edge Relaxation): When standing at state $x$, iterate over all incoming edges $u \to x$:
dp[x] = min(dp[x], dp[u] + cost(u, x)). Ideal when in-neighbors are easy to enumerate and allows immediate register accumulation ofdp[x]. - Push DP (Out-Edge Relaxation): Once
dp[u]is finalized, iterate over all outgoing edges $u \to v$:dp[v] = min(dp[v], dp[u] + cost(u, v)). Ideal when unreachable states can be skipped (if (dp[u] == INF) continue;) or when outgoing transitions are cleaner to express than incoming ones.
Hardware Reality — Pull DP Register Accumulation vs. Push DP Store-to-Load Forwarding
In a tight inner loop, Pull DP accumulates best = std::min(best, dp[u] + w) inside a single CPU register (%rax) and performs one memory write dp[x] = best at the end of the loop. In contrast, Push DP repeatedly reads and writes different memory addresses dp[u + step], which can stall the CPU's Store-to-Load forwarding buffer if addresses alias or exceed L1 cache lines. Conversely, when 95% of the state space is unreachable (dp[u] == INF), Push DP skips the inner loop entirely via a single branch, running orders of magnitude faster!
3. Complexity Matrix
Observe why 0/1 Knapsack iterates capacity w downwards (preventing item reuse), how Patience Sorting finds LIS in O(N log N), and how Myers Diff slides along diagonal snakes k = x - y.
Invariant & State
| Subproblem Domain | Number of States $|V|$ | Transitions per State | Total Time $O(|V| + |E|)$ | State Space Size |
|---|---|---|---|---|
| 1D Prefix / Suffix ($A[0..i]$) | O(N) | O(1) or O(N) | O(N) or O(N^2) | O(N) |
| Pair of Prefixes ($A[0..i], B[0..j]$) | O(N * M) | O(1) | O(N * M) | O(N * M) |
| 2D Contiguous Subarray ($A[i..j]$) | O(N^2) | O(j - i) | O(N^3) | O(N^2) |
| Subset Bitmask ($S \subseteq \{0..N-1\}$) | O(2^N) | O(N) | O(N * 2^N) | O(2^N) |
4. Reference C++20 Implementation
#include <algorithm>
#include <cstdint>
#include <limits>
#include <vector>
// Minimum Coin Change with Full Optimal Solution Reconstruction (DAG Shortest Path + Parent Pointers)
struct CoinChangeResult {
int min_coins; // -1 if unreachable
std::vector<int> chosen_coins;
};
CoinChangeResult solve_coin_change_with_reconstruction(const std::vector<int>& coins, int amount) {
constexpr int INF = 1'000'000'000;
// S (Subproblems): dp[x] = min coins to form exact sum x in [0..amount]
std::vector<int> dp(amount + 1, INF);
std::vector<int> parent_coin(amount + 1, -1);
// B (Base Case): 0 coins needed to form sum 0
dp[0] = 0;
// T (Topological Order): x = 1 .. amount (since coins > 0, u = x - c < x is acyclic!)
for (int x = 1; x <= amount; ++x) {
int best = INF;
int best_c = -1;
// R (Relate - Pull DP): dp[x] = 1 + min_{c in coins} dp[x - c]
for (int c : coins) {
if (x >= c && dp[x - c] + 1 < best) {
best = dp[x - c] + 1;
best_c = c;
}
}
dp[x] = best;
parent_coin[x] = best_c;
}
if (dp[amount] >= INF) {
return { -1, {} };
}
// Backpointer Traversal along the Implicit DAG from sink amount back to source 0
std::vector<int> used;
for (int cur = amount; cur > 0; cur -= parent_coin[cur]) {
used.push_back(parent_coin[cur]);
}
return { dp[amount], std::move(used) };
}Production Pitfall — Cyclic State Transitions & Sentinel Overflow (INF + cost)
Two errors break DP solvers in production: First, if a coin can have value $c = 0$ (or negative weight cycles exist), the transition $x \to x - 0$ is a self-loop ($G$ is no longer a DAG!). Second, initializing unreachable states to std::numeric_limits<int>::max() and evaluating dp[x - c] + 1 causes signed 32-bit integer overflow (Undefined Behavior in C++, wrapping around to INT_MIN and corrupting std::min). Always use a safe sentinel such as 1'000'000'000 (0x3f3f3f3f) so INF + cost cannot overflow.