Dynamic Programming

Naive recursion can solve the same state repeatedly. Dynamic programming (DP) identifies the distinct subproblems, solves each once, and reuses its result. The technique applies when subproblems overlap and their answers combine into solutions of larger states. Its central work is not allocating a table; it is defining exactly what each state means and proving the recurrence that relates states.

DP Properties

A problem is a good candidate for dynamic programming when it has both of these properties:

1. Optimal substructure — an optimal solution can be assembled from optimal solutions to appropriate subproblems. For example, every segment of a shortest path is itself shortest between its endpoints; otherwise replacing that segment would improve the complete path.
2. Overlapping subproblems — a direct recursive formulation reaches the same semantic states repeatedly. Merge sort instead recurses on disjoint array ranges, so caching does not remove repeated states.

Caching changes the bound from the number of recursive visits to approximately number of reachable states * transition cost per state. This can turn an exponential recursion into polynomial time when the state space and transitions are polynomial, as in Fibonacci. DP is not automatically polynomial: a formulation may itself have exponentially many distinct states.

Binary search, quicksort partitioning, and divide-and-conquer maximum subarray create disjoint subproblems, so they do not need DP caching. Recursive syntax alone is not a DP signal; repeated semantic states are.

State Design

State Meaning

A state is the smallest collection of facts needed to describe one subproblem. Define it in a complete sentence before writing a table. For example, dp[i][w] might mean “the maximum value obtainable from the first i items with capacity w.” Omitting necessary facts merges different subproblems and makes the recurrence incorrect; storing unnecessary facts enlarges the state space.

Transitions

A transition expresses one state through smaller states. Enumerate the legal final or next choices and specify which predecessor each choice requires. For an optimization problem, the transition usually takes a minimum or maximum over those alternatives; for a counting problem, it usually sums them. The transition is valid only if the predecessor states contain all information needed by the choice.

Base States

Base states are subproblems answerable without another transition. Their values anchor the recurrence. In minimum-coin change, amount zero needs zero coins; in LCS, a prefix paired with an empty prefix has length zero. Distinguish an unreachable state from a legitimate numeric answer by using a separate flag or a sentinel outside the result domain.

Evaluation Order

Dependencies determine evaluation order. Every top-down call must approach a base state, and every bottom-up predecessor must be computed before the state that reads it. Draw arrows from each state to its dependencies when the order is unclear. The same dependency analysis reveals whether old rows can be overwritten and whether loop direction changes the problem’s meaning.

Decide early whether the interface needs only an optimal value or an actual witness. Witness recovery may require stored predecessor choices or table entries that a value-only space optimization would otherwise discard.

Evaluation Styles

Two evaluation styles eliminate repeated states.

Memoization

Memoization (top-down) retains recursion and checks a cache before solving a state.

#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>

#define UNSOLVED LLONG_MIN

long long fib_memo(int n, long long memo[]) {
    if (n < 2) {
        return n;
    }
    if (memo[n] != UNSOLVED) {
        return memo[n];                          /* already solved: reuse it */
    }
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

bool fibonacci_top_down(int n, long long *out) {
    if (out == NULL || n < 0 || n > 92) {
        return false;
    }
    size_t count = (size_t) n + 1U;
    long long *memo = malloc(count * sizeof(*memo));
    if (memo == NULL) {
        return false;
    }
    for (int i = 0; i <= n; i++) {
        memo[i] = UNSOLVED;
    }
    *out = fib_memo(n, memo);
    free(memo);
    return true;
}

Tabulation

Tabulation (bottom-up) evaluates base states first and then follows a dependency order in which every required predecessor is already available.

#include <stdbool.h>
#include <stdlib.h>

bool fibonacci_bottom_up(int n, long long *out) {
    if (out == NULL || n < 0 || n > 92) {
        return false;
    }
    if (n < 2) {
        *out = n;
        return true;
    }
    size_t count = (size_t) n + 1U;
    long long *table = malloc(count * sizeof(*table));
    if (table == NULL) {
        return false;
    }
    table[0] = 0;
    table[1] = 1;
    for (int i = 2; i <= n; i++) {
        table[i] = table[i - 1] + table[i - 2];   /* every value needed already sits in the table */
    }
    *out = table[n];
    free(table);
    return true;
}

Both solve each distinct state fib(k) once, giving Theta(n) time instead of the naive exponential call tree.

fibonacci_bottom_up needs only the two most recent entries. Rolling those values through two scalars reduces auxiliary space from O(n) to O(1). This optimization is valid because no later state refers further back; DPs with wider dependencies or witness recovery may need more of the table.

Memoization visits only states reachable from the requested state and often follows directly from a recurrence. Tabulation avoids recursive stack depth and can improve memory locality, but may fill states that a particular input never needs. Converting between them requires identifying a table order consistent with the dependency graph. Cyclic dependencies cannot be tabulated by a simple topological order; they need a reformulation, a graph algorithm, or repeated relaxation with a separately proved convergence condition.

Coin Change

Coin-change problems illustrate how a small wording change alters state and recurrence.

Minimum coins. Given positive denominations and target T, find the fewest coins whose values sum to T, with unlimited copies. Define dp[x] as the fewest coins forming exact amount x:

Unreachable states remain infinity.

#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

int minimum_coins(const int coins[], size_t coin_count, int target,
                  int chosen_coin[]) {
    if (target < 0 || target == INT_MAX ||
        (coin_count > 0U && coins == NULL)) {
        return -1;
    }
    for (size_t i = 0; i < coin_count; i++) {
        if (coins[i] <= 0) {
            return -1;
        }
    }
    uintmax_t state_count = (uintmax_t) (unsigned int) target + 1U;
    if (state_count > SIZE_MAX / sizeof(int)) {
        return -1;
    }

    int *dp = malloc((size_t) state_count * sizeof(*dp));
    if (dp == NULL) {
        return -1;
    }
    dp[0] = 0;
    if (chosen_coin != NULL) {
        chosen_coin[0] = -1;
    }

    for (size_t amount = 1; amount < (size_t) state_count; amount++) {
        dp[amount] = INT_MAX;
        if (chosen_coin != NULL) {
            chosen_coin[amount] = -1;
        }
        for (size_t i = 0; i < coin_count; ++i) {
            size_t coin = (size_t) coins[i];
            if (coin > amount || dp[amount - coin] == INT_MAX) {
                continue;
            }
            if (dp[amount - coin] + 1 < dp[amount]) {
                dp[amount] = dp[amount - coin] + 1;
                if (chosen_coin != NULL) {
                    chosen_coin[amount] = (int) coin;
                }
            }
        }
    }

    int answer = (dp[target] == INT_MAX) ? -1 : dp[target];
    free(dp);
    return answer;
}

For coins {1,3,4} and target 6:

amount: 0 1 2 3 4 5 6
dp:     0 1 2 1 1 2 2

The optimum is two coins 3+3; the greedy largest-first choice 4+1+1 uses three. Following chosen_coin[6], subtracting each recorded coin until amount zero, reconstructs an optimum.

Counting combinations needs a different meaning: ways[x] counts unordered combinations forming x. Initialize ways[0]=1, loop over coins outside and amounts upward inside. Reversing those loops counts ordered sequences instead. Loop order is therefore part of the recurrence’s semantics, not a micro-optimization.

Minimum coins takes Theta(coin_count * target) time and Theta(target) space. Positive denominations are required; a zero or negative coin destroys the finite, forward dependency structure. This compact implementation also requires target < INT_MAX, reserving INT_MAX exclusively for an unreachable state; without that restriction, denomination 1 and target INT_MAX would have a valid optimum indistinguishable from the sentinel. If chosen_coin is non-null, its caller must provide target + 1 writable elements. The return value -1 combines invalid input, allocation failure, and an unreachable target; a production API should distinguish those statuses.

Zero-One Knapsack

In 0–1 knapsack, n items have weights and values, total capacity is W, and each item may be taken whole or omitted. The objective is maximum total value without exceeding capacity.

Define state (i,w) as the best value obtainable from the first i items with capacity w. Item i-1 is either omitted, retaining state (i-1,w), or included once when it fits, adding its value to state (i-1,w-weight[i-1]). The larger valid alternative defines the recurrence.

#include <stdbool.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

bool knapsack(int capacity, const int weights[], const long long values[],
              size_t n, long long *out) {
    if (capacity < 0 || out == NULL ||
        (n > 0U && (weights == NULL || values == NULL))) {
        return false;
    }
    for (size_t i = 0; i < n; i++) {
        if (weights[i] < 0) {
            return false;
        }
    }
    if (n == SIZE_MAX) {
        return false;
    }
    uintmax_t columns_wide = (uintmax_t) (unsigned int) capacity + 1U;
    if (columns_wide > SIZE_MAX) {
        return false;
    }
    size_t rows = n + 1U;
    size_t columns = (size_t) columns_wide;
    if (columns != 0U && rows > SIZE_MAX / columns) {
        return false;
    }
    size_t cells = rows * columns;
    if (cells > SIZE_MAX / sizeof(long long)) {
        return false;
    }
    long long *dp = calloc(cells, sizeof(*dp));
    if (dp == NULL) {
        return false;
    }

#define DP(i, w) dp[(i) * columns + (size_t) (w)]
    for (size_t i = 1; i <= n; i++) {
        for (size_t w = 0; w < columns; w++) {
            DP(i, w) = DP(i - 1U, w);
            if ((size_t) weights[i - 1U] <= w) {
                long long previous = DP(i - 1U,
                    w - (size_t) weights[i - 1U]);
                long long value = values[i - 1U];
                if ((value > 0 && previous > LLONG_MAX - value) ||
                    (value < 0 && previous < LLONG_MIN - value)) {
                    free(dp);
                    return false;
                }
                long long with_item = previous + value;
                if (with_item > DP(i, w)) {
                    DP(i, w) = with_item;
                }
            }
        }
    }

    *out = DP(n, capacity);
#undef DP
    free(dp);
    return true;
}

The table has (n + 1)(W + 1) cells and constant transition work per cell, giving Theta(nW) time and space. This is pseudo-polynomial because W is a numeric magnitude whose binary representation has only Theta(log W) bits. A billion-column table is infeasible even when the item count is small.

Solution Recovery

A DP value may answer “how good?” without answering “which choices?” Recover a witness in one of two ways:

1. store the chosen predecessor while filling each state;
2. infer a predecessor later by comparing the completed state’s value with the values that could have produced it.

For 0–1 knapsack at state (i,w), if dp[i][w] == dp[i-1][w], an optimum exists that omits item i-1. Otherwise the item was included under the selected tie policy; record it and continue at (i-1, w-weight[i-1]). For LCS, equal final characters move diagonally and emit that character; otherwise move toward a neighboring cell with the larger value.

Recovery follows at most one predecessor per state, typically adding O(number of decisions) time. Ties can represent several optimal solutions. A deterministic implementation must state its tie rule; enumerating every optimum may require exponential output. Space compression can discard the predecessor information needed for recovery, so value-only and witness-returning interfaces may justify different implementations.

Longest Common Subsequence

Given two sequences, a subsequence remains after deleting zero or more elements without changing the order of those retained. "ACE" is a subsequence of "ABCDE" but is not a substring because its positions are not contiguous. The longest common subsequence (LCS) problem asks for a longest sequence that is a subsequence of both inputs.

Let dp[i][j] be the LCS length of prefixes a[0..i) and b[0..j). When the final characters match, call the common character x. Appending x to an LCS of a[0..i-1) and b[0..j-1) constructs a common subsequence of length dp[i-1][j-1] + 1, giving a lower bound. For the upper bound, take an optimal common subsequence of the full prefixes. An optimum can be chosen to end with their shared final character: if it does not already, append or exchange its last occurrence for the later matching x without invalidating subsequence order. Removing that final x leaves a common subsequence of the two shorter prefixes, whose length is at most dp[i-1][j-1]. Therefore equality holds. If the final characters differ, no common subsequence can use both as its final matched symbol, so an optimum omits at least one of them and has length max(dp[i-1][j], dp[i][j-1]).

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

bool lcs_length(const char *a, const char *b, size_t *out) {
    if (a == NULL || b == NULL || out == NULL) {
        return false;
    }
    size_t m = strlen(a);
    size_t n = strlen(b);
    if (m == SIZE_MAX || n == SIZE_MAX) {
        return false;
    }
    size_t rows = m + 1U;
    size_t columns = n + 1U;
    if (columns != 0U && rows > SIZE_MAX / columns) {
        return false;
    }
    size_t cells = rows * columns;
    if (cells > SIZE_MAX / sizeof(size_t)) {
        return false;
    }
    size_t *dp = calloc(cells, sizeof(*dp));
    if (dp == NULL) {
        return false;
    }

#define DP(i, j) dp[(i) * columns + (j)]
    for (size_t i = 1; i <= m; i++) {
        for (size_t j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1]) {
                DP(i, j) = DP(i - 1U, j - 1U) + 1U;
            } else {
                DP(i, j) = (DP(i - 1U, j) > DP(i, j - 1U))
                    ? DP(i - 1U, j) : DP(i, j - 1U);
            }
        }
    }

    *out = DP(m, n);
#undef DP
    free(dp);
    return true;
}

This runs in Theta(mn) time and space, polynomial in the actual string lengths.

LCS Table

For a="ABCBDAB" down the rows and b="BDCABA" across the columns, the complete length table is:

The bottom-right value is 4. To recover one sequence, start there. On equal final characters, emit the character and move diagonally. On a mismatch, move to a neighbor with the same optimal value; a tie policy chooses among multiple LCSs. Choosing the upper cell on ties yields the reverse emissions A,B,C,B, hence LCS "BCBA" after reversal. A different tie path can produce "BDAB"; both satisfy the length and subsequence contracts.

The table below can be filled cell by cell, with the active recurrence and recovery path visible:

Computing row i needs the preceding row and the current row’s left neighbor, so length-only storage can be compressed to two rows and Theta(min(m,n)) space by placing the shorter string across the columns. Ordinary table-walking reconstruction needs all decisions.

Hirschberg reconstruction recovers a sequence with linear auxiliary space. Split a at its midpoint. Two-row DP computes LCS lengths between the left half and every prefix of b; a reverse pass computes lengths between the right half and every suffix of b. Choose the split position in b maximizing the sum of those two lengths, then recurse on the two paired rectangles. If the parent rectangle has area mn and b splits at k, the child areas sum to (m/2)k + (m/2)(n-k) = mn/2. Work across recursion depths is therefore a geometric series mn + mn/2 + mn/4 + ... = Theta(mn), while auxiliary storage remains Theta(min(m,n)). The method trades a simple backward table walk for divide-and-conquer recomputation.

Maximum Subarray

The maximum-subarray problem asks for a contiguous run with maximum sum. A precise endpoint state improves the O(n log n) divide-and-conquer solution to a linear scan. The implementation below requires n > 0 and assumes every intermediate sum fits in int.

Define best_ending_here[i] = the maximum sum of any subarray that ends exactly at index i (not “somewhere in the first i elements” — exactly at i; that precision is the entire trick). Here’s the key recursive insight: a subarray ending at index i is either just the single element arr[i] (if extending any subarray ending at i - 1 would only drag the sum down), or it’s “the best subarray ending at i - 1” with arr[i] tacked onto the end. There is no third option — and that’s exactly what makes this a clean recurrence:

best_ending_here[i] = max(arr[i], best_ending_here[i - 1] + arr[i])

The overall answer is simply the largest value across all best_ending_here[i]. And now watch the rolling-variable optimization from the Fibonacci discussion reappear, in a more consequential setting: computing best_ending_here[i] only ever needs best_ending_here[i - 1] — never anything further back — so the entire array collapses into a single running variable:

int max_subarray_kadane(const int arr[], int n) {
    int best_ending_here = arr[0];
    int best_overall = arr[0];

    for (int i = 1; i < n; i++) {
        /* extend the previous best subarray, or start fresh at arr[i] — whichever is larger */
        best_ending_here = (best_ending_here + arr[i] > arr[i]) ? best_ending_here + arr[i] : arr[i];
        if (best_ending_here > best_overall) {
            best_overall = best_ending_here;
        }
    }
    return best_overall;
}

Kadane’s algorithm runs in Theta(n) time and Theta(1) auxiliary space. Its improvement comes from a stronger state characterization, not from a faster implementation of the same divide-and-conquer decomposition. Multiple techniques can solve one problem, and their state models determine the attainable bound.

Longest Increasing Subsequence

Given an array, find the length of the longest strictly increasing subsequence — a subset of elements (not necessarily contiguous) that are in strictly ascending order. For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4 (e.g. [2, 3, 7, 101]).

State: lis_ending_at[i] = length of the longest increasing subsequence that ends exactly at index i. This is the Kadane-style trick again — pinning the endpoint converts a global problem into a family of local ones.

Recurrence: to extend a subsequence to include arr[i], we can append arr[i] to any subsequence ending at some j < i where arr[j] < arr[i]. So:

lis_ending_at[i] = 1 + max(lis_ending_at[j]) for all j < i where arr[j] < arr[i]

Base case: every single element is a length-1 increasing subsequence.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

bool lis_length(const int arr[], size_t n, size_t *out) {
    if (out == NULL || (n > 0U && arr == NULL)) {
        return false;
    }
    if (n == 0U) {
        *out = 0U;
        return true;
    }
    if (n > SIZE_MAX / sizeof(size_t)) {
        return false;
    }
    size_t *dp = malloc(n * sizeof(*dp));
    if (dp == NULL) {
        return false;
    }
    for (size_t i = 0; i < n; i++) {
        dp[i] = 1U;                                /* each element alone */
    }

    for (size_t i = 1; i < n; i++) {
        for (size_t j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[j] + 1U > dp[i]) {
                dp[i] = dp[j] + 1U;
            }
        }
    }

    size_t best = 0U;
    for (size_t i = 0; i < n; i++) {
        if (dp[i] > best) {
            best = dp[i];
        }
    }

    *out = best;
    free(dp);
    return true;
}

This runs in Theta(n^2) time and Theta(n) space. To reconstruct a subsequence, keep a parent[] entry recording which j produced each best extension. On [3,10,2,1,20], the final lengths are [1,2,1,1,3], and one recovered length-three subsequence is [3,10,20].

Minimal Tails

The faster method changes the stored state. For every attainable length L, retain the smallest possible final value of an increasing subsequence of length L seen so far. A smaller tail is never worse: it leaves at least as many future values available for extension.

Because these minimal tails are strictly increasing by length, binary search finds the first tail greater than or equal to the current value x. Replacing that tail improves a state of the same length; appending after all tails creates a longer subsequence. For strict increase, use the first >= x; using the first > x instead computes a longest non-decreasing subsequence.

After processing a prefix, the invariant is: for every 1 <= L <= length, tail_index[L-1] ends an actual increasing subsequence of length L, and its value is the smallest possible tail among all such subsequences in the prefix. Replacing position L-1 uses the established length-L-1 predecessor, so existence is preserved. Minimality follows because binary search selects the first tail not smaller than x; shorter tails are below x, while any state of length at least L cannot obtain a smaller new tail from this x. Induction proves both that length never exceeds the true LIS and that every longer subsequence encountered extends the structure, so the final length is exact.

The following implementation returns source indices for one strict LIS and reports required output capacity separately:

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef enum {
    LIS_OK,
    LIS_INVALID,
    LIS_ALLOCATION_FAILED,
    LIS_OUTPUT_SMALL
} LisStatus;

LisStatus lis_indices(const int arr[], size_t n, size_t output[],
                      size_t output_capacity, size_t *out_length) {
    if (out_length == NULL || (n > 0U && arr == NULL) ||
        (output_capacity > 0U && output == NULL) ||
        n > SIZE_MAX / sizeof(size_t)) {
        return LIS_INVALID;
    }
    if (n == 0U) {
        *out_length = 0U;
        return LIS_OK;
    }

    size_t *tail_index = malloc(n * sizeof(*tail_index));
    size_t *parent = malloc(n * sizeof(*parent));
    if (tail_index == NULL || parent == NULL) {
        free(tail_index);
        free(parent);
        return LIS_ALLOCATION_FAILED;
    }

    size_t length = 0U;
    for (size_t i = 0U; i < n; i++) {
        size_t lo = 0U;
        size_t hi = length;
        while (lo < hi) {
            size_t mid = lo + (hi - lo) / 2U;
            if (arr[tail_index[mid]] < arr[i]) {
                lo = mid + 1U;
            } else {
                hi = mid;
            }
        }

        parent[i] = (lo == 0U) ? SIZE_MAX : tail_index[lo - 1U];
        tail_index[lo] = i;
        if (lo == length) {
            length++;
        }
    }

    *out_length = length;
    if (output_capacity < length || output == NULL) {
        free(parent);
        free(tail_index);
        return LIS_OUTPUT_SMALL;
    }

    size_t index = tail_index[length - 1U];
    for (size_t position = length; position > 0U; position--) {
        output[position - 1U] = index;
        index = parent[index];
    }

    free(parent);
    free(tail_index);
    return LIS_OK;
}

After processing each value of [10,9,2,5,3,7,101,18], the minimal tail values are:

The final length is four. Minimal-tail values alone need not describe one consistent source-index chain after replacements, so the code stores the index ending each length and a parent for every processed element. Following parents from the last length-four tail recovers indices for [2,3,7,18]. Each of n values performs one binary search over at most n tails, giving Theta(n log n) time and Theta(n) reconstruction storage.

Matrix-Chain Multiplication

Given matrices M₀, M₁, …, M_{n-1} where matrix Mᵢ has dimensions dims[i] × dims[i+1], find the order of multiplication that minimises the total number of scalar multiplications. (Matrix multiplication is associative — the result is the same regardless of order — but the cost can differ wildly. For three matrices A(10×100), B(100×5), C(5×50): (AB)C costs 10·100·5 + 10·5·50 = 7500 multiplications; A(BC) costs 100·5·50 + 10·100·50 = 75000.)

This is interval DP: subproblems are contiguous ranges rather than prefixes. State dp[i][j] is the minimum cost to multiply matrices i through j.

For each split k, multiply chains [i..k] and [k+1..j], then combine their results at cost dims[i] * dims[k+1] * dims[j+1]. The recurrence takes the minimum over all splits. This implementation uses checked heap storage rather than a variable-length array, which is an optional feature in C17. The caller supplies n+1 positive dimensions for n>0; status values distinguish interface, allocation, and arithmetic failures.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef enum {
    MATRIX_CHAIN_OK,
    MATRIX_CHAIN_INVALID,
    MATRIX_CHAIN_ALLOCATION_FAILED,
    MATRIX_CHAIN_OVERFLOW
} MatrixChainStatus;

static bool multiply_u64(uint64_t a, uint64_t b, uint64_t *product) {
    if (a != 0U && b > UINT64_MAX / a) {
        return false;
    }
    *product = a * b;
    return true;
}

static bool add_u64(uint64_t a, uint64_t b, uint64_t *sum) {
    if (b > UINT64_MAX - a) {
        return false;
    }
    *sum = a + b;
    return true;
}

MatrixChainStatus matrix_chain_order(const uint64_t dims[], size_t n,
                                     uint64_t *minimum) {
    if (dims == NULL || minimum == NULL || n == 0U ||
        n > SIZE_MAX / n) {
        return MATRIX_CHAIN_INVALID;
    }
    size_t cells = n * n;
    if (cells > SIZE_MAX / sizeof(uint64_t)) {
        return MATRIX_CHAIN_INVALID;
    }
    for (size_t i = 0; i <= n; ++i) {
        if (dims[i] == 0U) {
            return MATRIX_CHAIN_INVALID;
        }
    }

    uint64_t *dp = malloc(cells * sizeof(*dp));
    if (dp == NULL) {
        return MATRIX_CHAIN_ALLOCATION_FAILED;
    }
    for (size_t i = 0; i < n; ++i) {
        dp[i * n + i] = 0U;
    }

    for (size_t length = 2; length <= n; ++length) {
        for (size_t i = 0; i <= n - length; ++i) {
            size_t j = i + length - 1U;
            uint64_t best = 0U;
            bool found = false;
            for (size_t k = i; k < j; ++k) {
                uint64_t scalar_cost = 0U;
                uint64_t partial = 0U;
                uint64_t candidate = 0U;
                if (!multiply_u64(dims[i], dims[k + 1U], &partial) ||
                    !multiply_u64(partial, dims[j + 1U], &scalar_cost) ||
                    !add_u64(dp[i * n + k], dp[(k + 1U) * n + j],
                             &partial) ||
                    !add_u64(partial, scalar_cost, &candidate)) {
                    continue;
                }
                if (!found || candidate < best) {
                    best = candidate;
                    found = true;
                }
            }
            if (!found) {
                free(dp);
                return MATRIX_CHAIN_OVERFLOW;
            }
            dp[i * n + j] = best;
        }
    }

    *minimum = dp[n - 1U];
    free(dp);
    return MATRIX_CHAIN_OK;
}

The fill order—by increasing chain length—is required because a chain of length len depends only on shorter chains. For dimensions [10,100,5,50], length-two states are dp[0][1]=5,000 and dp[1][2]=25,000. The length-three state compares:

The second split records (M0 M1) M2.

With n matrices, the number of full binary parenthesizations is the Catalan number $C_{n-1}$. It satisfies $C_0=1$ and $C_k=\sum_{i=0}^{k-1} C_i C_{k-1-i}$ over all root splits, and grows as Theta(4^n/n^(3/2)). Enumerating those trees is exponential. The DP merges identical interval subproblems, fills Theta(n^2) intervals, and tests at most n splits per interval, giving Theta(n^3) time and Theta(n^2) space.

The “try every split point” recurrence is the characteristic interval-DP shape. It is valid only after proving that once split k is chosen, optimal solutions for [i..k] and [k+1..j] can be combined independently and that the stated multiplication term accounts for their interaction. Other interval problems require their own state and combine proof; recognizing a loop shape does not supply the recurrence automatically.

Space Optimization

Dependency distance determines how much history must remain stored.

• Fibonacci needs two preceding scalar states.
• Kadane needs one preceding scalar plus the best global value.
• 0–1 knapsack can use one row if capacities iterate downward, preventing the current item from being reused.
• Unbounded knapsack iterates capacities upward because reusing the current item is permitted.
• LCS length needs the previous row and current-row prefix, reducing space to Theta(min(m,n)).
• Matrix-chain multiplication depends on many smaller intervals and retains a triangular Theta(n^2) table.

Before overwriting a table dimension, list every dependency and ensure its old value will never be needed again. Loop direction can distinguish a correct 0–1 algorithm from an accidentally unbounded one. Also account for witness recovery: Hirschberg’s divide-and-conquer LCS recovers a sequence in linear space, but an ordinary two-row optimization returns only the length.

Pseudo-Polynomial Time

Knapsack and coin change run in time polynomial in a numeric bound such as capacity W or target T. If W is encoded in binary, its representation length is Theta(log W), and a table with W+1 columns can be exponential in that length. Such algorithms are pseudo-polynomial, not polynomial in total encoded input size.

This distinction coexists consistently with NP-completeness. A subset-sum target of 1,000 is manageable; a target represented by a 200-bit integer is potentially around 2^200, and a target-indexed table is physically impossible. Pseudo-polynomial methods remain extremely valuable when numeric bounds are naturally small, unary-encoded, or limited by the application.

DP Review

• Dynamic programming applies when subproblems overlap and larger answers have justified optimal substructure.
• State meaning, transitions, base states, and evaluation order must be defined before table code.
• Memoization follows demand recursively; tabulation orders all relevant states explicitly.
• Coin change, 0–1 knapsack, LCS, LIS, maximum subarray, and matrix chains demonstrate amount, prefix, endpoint, and interval states.
• Parent decisions or table comparisons recover witnesses; ties and compressed storage affect recovery semantics.
• Space optimization follows dependency width, and iteration direction can change whether choices are reusable.
• Bounds indexed by numeric values may be pseudo-polynomial in encoded input length.

DP Problems

State Sentences

1. Write one complete state-meaning sentence, recurrence, and base states for staircase counting with steps of sizes one or two.
2. Decide whether DP is useful for unweighted shortest path, merge sort, maximum a[i]+b[j] with i<j, and exact string edit distance. Identify overlap and state size rather than relying on problem labels.
3. Give two different correct state definitions for minimum coin change—amount-only and (coin_prefix,amount)—and explain which questions each can answer.
4. For every chapter example, list the input parameters that determine the number of states and the transition cost per state.

Table Traces

5. Fill minimum-coin tables for denominations {1,3,4} and targets 0..10; recover one optimum per target and record tie behavior.
6. Fill the full 0–1 knapsack table for weights [2,3,4,5], values [3,4,5,8], and capacity 8. Recover the selected items.
7. Fill the LCS table for "AGGTAB" and "GXTXAYB", then recover every distinct LCS without emitting duplicates.
8. Trace Kadane’s endpoint state on an all-negative array and on [4,-1,2,1,-7,5]. Explain why initializing the best sum to zero changes the nonempty-subarray contract.
9. Trace both LIS implementations on [3,4,-1,0,6,2,3]. Record quadratic endpoint lengths, minimal tails, parent indices, and one recovered subsequence.

Transition Proofs

10. Prove minimum coin change’s recurrence by considering the final coin. State why positive denominations make dependencies well founded.
11. Prove both branches of the LCS recurrence, including the matching-final-character upper bound and the mismatching-character omission argument.
12. Prove that 0–1 knapsack capacity must iterate downward in a one-row implementation. Give a smallest upward-loop counterexample that reuses one item.
13. Prove the minimal-tail LIS invariant and explain why lower_bound computes strict increase while upper_bound computes non-decrease.
14. Prove matrix-chain optimal substructure by replacing one nonoptimal subchain inside an allegedly optimal parenthesization.

Memory Layout

15. Convert Fibonacci, Kadane, LCS length, and 0–1 knapsack to their smallest value-only storage. For each, list the overwritten dependencies that justify the reduction.
16. Implement one-row 0–1 knapsack with checked value addition. Add predecessor information or explain why straightforward one-row overwriting complicates witness recovery.
17. Implement Hirschberg reconstruction from two-row LCS length passes. Compare emitted tie choices with full-table recovery.
18. Change lis_indices into a two-call API: the first call reports required output length and the second fills caller storage. Keep invalid input, allocation failure, and insufficient capacity distinguishable.

DP Designs

19. Derive edit distance with insertion, deletion, and substitution costs. Recover one edit script and define tie behavior.
20. Given a grid with blocked cells and nonnegative cell costs, design minimum-cost path and path-count DPs. State how the recurrence changes when diagonal moves are allowed.
21. Design interval DP for minimum-cost polygon triangulation. Define the subpolygon state, split transition, base range, and reconstruction data.
22. Design a DP for weighted interval scheduling after sorting by finish time. Precompute the previous compatible interval with binary search and prove the include/exclude recurrence.

State-Space Limits

23. Compare target-indexed subset-sum DP, a bitset implementation, meet-in-the-middle, and backtracking when n=40 but target values have 200 bits.
24. A digit-DP task asks how many integers in [0,N] avoid two consecutive equal digits. Define position, tightness, started-state, and previous-digit dimensions without counting leading padding as real digits.
25. Design a tree DP for maximum-weight independent set on a tree. Give include/exclude states and prove children become independent after fixing the parent choice.
26. Derive a profile DP for domino tilings of an r x c board when r is small. Explain why the 2^r mask makes the method fixed-parameter rather than polynomial in unrestricted r.