Dynamic Programming (DP)¶

Dynamic Programming (DP) is a methodical paradigm for solving complex optimization problems by breaking them into simpler, overlapping subproblems, solving each once, and storing solutions for reuse—thus avoiding redundant recomputation. Coined by Richard Bellman in the 1950s (from "dynamic" for staged decisions and "programming" for planning), DP exploits two hallmarks: optimal substructure (optimal solution built from optimal subsolutions) and overlapping subproblems (subproblems recur exponentially in naive recursion). It transforms exponential-time brute force into polynomial via memoization or tabulation, underpinning fields from operations research to AI. Unlike greedy (local optima), DP guarantees global via exhaustive subs.

1. Core Mechanics¶

DP formulates problems as recurrences: f(i) = opt { g(j) + h(i,j) | j < i }, solved via table T[state] storing f.

State Definition: Minimal info capturing subproblem (e.g., fib(n): position n; knapsack(i,w): first i items, capacity w).
Transition: How to compute T[state] from prior T[prev] (e.g., fib(n) = fib(n-1) + fib(n-2)).
Base Cases: T[0/∅] = 0/1.
Filling Order: Bottom-up (small to large states); top-down (recurse with memo).
Top-Down (Memoization): Recursive with cache (dict/array); compute on-demand.
- Pros: Lazy (only needed states); recursive intuition.
- Cons: Stack overflow O(depth); cache misses.
Bottom-Up (Tabulation): Iterative loop over states; fill table exhaustively.
- Pros: No recursion; predictable space.
- Cons: Computes unused states.

Pseudocode Template (Bottom-Up 1D):

function DP(state_size: int, base: func(state: int) -> val): table
    table = array<val>(state_size + 1)
    for i from 0 to state_size:
        if i == 0:  // Base
            table[i] = base(i)
        else:
            table[i] = INF  // Or 0
            for j from 0 to i-1:  // Transition
                table[i] = opt(table[i], table[j] + cost(i,j))
    return table

2. Complexity Analysis¶

DP time/space = #states × #transitions per state.

Time Complexity:

Problem Type #States Transitions/State Total Time

1D (Fib) O(n) O(1) O(n)

2D (LCS) O(n m) O(1) O(n m)

Knapsack O(n W) O(n) O(n² W)
- Derivation: Exhaustive fill; opt=min/max O(1). Space O(states) base; optimized O(min dims).
Space Complexity: Table O(states); recursion O(depth × frame).
- Trade-Off: Time for space (e.g., O(n) space for O(n²) time via rolling).
Average/Worst: Dense states O(states × trans); sparse memo O(visited).

3. Derivations and Theoretical Foundations¶

Recurrence Derivation: From problem: Optimal f(n) = max/min over choices {f(sub) + marginal}.
- Overlapping: Naive recurse T(2^n); DP O(poly) via cache.
Optimal Substructure: Lemma: If optimal sol contains optimal sub-sol, DP works.
- Proof Sketch: Contradiction: If sub non-optimal, replace → better global.
DP Table as DAG: States as nodes, transitions edges; longest path O(states) if acyclic.

4. Proofs of Correctness and Optimality¶

Memo Correctness: Top-down: Cache hit = prior compute (induction on call depth); miss = recurse to base.
Tabulation Order: If dependencies small-to-large (topo order), each T[i] uses computed priors → correct.
Optimality Proof (General): By induction on subproblem size.
- Base: Trivial optimal.
- Inductive: Assume subs optimal; f(i) = opt over optimal subs + marginal → global optimal (substructure).
No Overcount: Cache ensures each state once.

5. Classic Examples¶

Fibonacci: 1D Chain
- Rec: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1.
- Table: T[0]=0, T[1]=1; T[i]=T[i-1]+T[i-2].
- Complexity: O(n) time/space.
- Space Opt: O(1) (two vars).
Pseudocode (Bottom-Up):
```
function fibonacci(n: int): long
    if n <= 1: return n
    a, b = 0, 1
    for i from 2 to n:
        a, b = b, a + b
    return b
```

0/1 Knapsack: 2D Resource

Rec: K(i,w) = max{ K(i-1,w), K(i-1,w-v_i) + p_i if w≥v_i }.
Table: T[0..n][0..W]=0; fill i=1 to n, w=0 to W.
Complexity: O(n W) time/space; W=capacity.
Space Opt: 1D T[0..W]; backward fill.

Pseudocode (2D Bottom-Up):

function knapsack(values: array<int>, weights: array<int>, W: int): int
    n = values.length
    T = 2D array[n+1][W+1] init 0
    for i from 1 to n:
        for w from 0 to W:
            if weights[i-1] <= w:
                T[i][w] = max(T[i-1][w], T[i-1][w - weights[i-1]] + values[i-1])
            else:
                T[i][w] = T[i-1][w]
    return T[n][W]

Longest Common Subsequence (LCS): 2D Alignment
- Rec: LCS(i,j) = LCS(i-1,j-1)+1 if match; max(LCS(i-1,j), LCS(i,j-1)) else.
- Table: T[0..m][0..n]=0; fill diagonals.
- Complexity: O(m n) time/space.
- Space Opt: O(min(m,n)).
Matrix Chain Multiplication: 2D Interval
- Rec: M(i,j) = min_{k=i..j-1} M(i,k) + M(k+1,j) + cost(A_i..A_j).
- Table: T[1..n][1..n]; fill len=2 to n, i=1 to n-len+1, j=i+len-1.
- Complexity: O(n³) time (n intervals, n k's); O(n²) space.

6. Advanced Variants¶

Space-Optimized DP: Rolling arrays (e.g., LCS O(n)); reconstruct via bits.
Parallel DP: Wavefront (diagonals in 2D); PRAM O(n / p + log n).
Stochastic DP: Expected values (MDP: Bellman eq V(s)=max_a [R(s,a) + γ ∑ P(s'|s,a) V(s')]); value/policy iteration.
Convex Hull Opt: For quadrangle ineq (e.g., knapsack concave), O(n²) to O(n log n) via hull.

7. Pros/Cons, Optimizations, and Practical Nuances¶

Pros: Guarantees optimal; handles constraints.
Cons: State explosion (curse of dimensionality); needs substructure.
Optimizations: Prune impossible states; memo dict for sparse.
Empirical: For n=1000 2D, O(10^6) fine; debug via table prints.

1D Dynamic Programming¶

1D Dynamic Programming (DP) refers to formulations where the state space is one-dimensional, typically indexed by a single parameter like position, length, or capacity—resulting in a linear table T[0..N] where each entry T[i] depends on a constant or linear number of previous entries. This simplicity yields O(N) time and space, making 1D DP the gateway to the paradigm, ideal for chain-like problems (e.g., sequences, paths) with local dependencies. Unlike 2D/ND DP (e.g., LCS O(NM)), 1D avoids quadratic explosion, often optimizable to O(1) space via sliding variables. Theoretical roots: Linear recurrences (e.g., Fibonacci as linear homogeneous); computability via matrix exponentiation O(log N).

1. Core Mechanics¶

1D DP solves f(N) by filling a table from base to N, where T[i] = opt over j < i { T[j] + marginal(i,j) }, often O(1) opts (e.g., last 1-2).

State Definition: T[i] = optimal value for first i items/subproblem size i (e.g., max profit up to day i).
Transition: T[i] = max/min { T[i-1] + c(i), T[i-2] + d(i), ... } (fixed window).
Base Cases: T[0]=0 (empty); T[1]=init.
Filling Order: Sequential i=0 to N (bottom-up); recurse with memo top-down.
Top-Down Example (Fib): Cache if T[n] computed; else recurse T[n]=T[n-1]+T[n-2].
Bottom-Up: Loop i=1 to N; T[i] from priors.

Pseudocode Template (Bottom-Up with O(1) Opts):

function oneD_DP(N: int, base: func(int) -> val, trans: func(int, array<val>) -> val): array<val>
    T = array<val>(N + 1)
    T[0] = base(0)
    for i from 1 to N:
        T[i] = trans(i, T[0..i-1])  // e.g., max(T[i-1], T[i-2] + c(i))
    return T

2. Complexity Analysis¶

1D DP's hallmark: O(N) time/space, with transitions O(1) or O(N) (rare, quadratic).

Time Complexity:

Transition Type Time Derivation

O(1) Opts (Fib) O(N) N steps × O(1)

O(N) Opts (Naive LIS) O(N²) N × avg N/2
- Details: Fill N+1 entries; each O(trans). Space O(N) table; O(1) sliding.
Space Complexity:

Variant Space Notes

Full Table O(N) T[0..N]

Sliding Vars O(1) Keep last k (e.g., Fib: prev2, prev1)
Average/Worst: Dense: O(N); sparse memo: O(visited ≤N).

3. Derivations and Theoretical Foundations¶

Recurrence Derivation: From chain: f(i) = opt {f(j) + c(j+1..i) | j\<i}; if local (j=i-1 or i-k), O(1).
Matrix Exponentiation: For linear rec T[i] = ∑ a_k T[i-k], [T[i]..T[i-k+1]] = M × [T[i-1]..T[i-k]]; T[N] = M^{N-1} × base vec; O(k³ log N) k=order.
- Fib: M = [[1,1],[1,0]]; F_n = M^{n-1} [1,0]^T (1,1).
Convex/Concave Opt: If cost quadrangle ineq, Knuth-Yao O(N) from O(N²).

4. Proofs of Correctness and Optimality¶

Induction on i: Base i=0/1 correct. Inductive: T[i] = opt over correct T[j\<i] + marginal → T[i] optimal (substructure).
Overlapping Reuse: Each sub i computed once; naive 2^{O(N)} → O(N).
Space Correctness (Sliding): If transition uses only last k, priors before i-k irrelevant (chain dep).

5. Classic 1D Examples¶

Fibonacci Numbers: Linear Recurrence
- State: T[i] = i-th Fib.
- Trans: T[i] = T[i-1] + T[i-2].
- Base: T[0]=0, T[1]=1.
- O(1) Space: a=0,b=1; loop a,b = b, a+b.
Pseudocode (O(1) Space):
```
function fib(n: int): long
    if n <= 1: return n
    a, b = 0, 1
    for _ from 2 to n:
        a, b = b, a + b
    return b
```
Coin Change (Min Coins for Amount N):
- State: T[i] = min coins for amount i.
- Trans: T[i] = min over coin c ≤i { T[i-c] +1 } or ∞.
- Base: T[0]=0; T[i]=∞ if no.
- Complexity: O(N C) C=#coins (pseudo-1D).
Longest Increasing Subsequence (LIS): Patience Sorting Variant
- State: T[i] = LIS ending at i.
- Trans: T[i] = 1 + max {T[j] | j\<i, arr[j]\<arr[i]} or 1.
- Complexity: O(N²) naive; O(N log N) binary search on tails.
- Space Opt: Keep tails array.
Edit Distance (1D Opt from 2D): For strings, rolling 1D T[0..M] for prev row.

6. Advanced Variants¶

Matrix Expo for Linear: O(k³ log N) for order-k rec; faster than O(N) for large N.
Parallel 1D DP: Prefix sums for opts; O(N/p + log N).
Stochastic 1D: Markov chains; expected T[i] = ∑ p_j T[j] + r_i.

7. Pros/Cons, Optimizations, and Practical Nuances¶

Pros: Simple linear; O(1) space easy.
Cons: O(N) space naive; transitions grow (e.g., unbounded knapsack O(N²)).
Optimizations: Sliding window; memo dict sparse.
Empirical: For N=10^6 Fib, O(1) instant; debug trace T.

8. Applications and Real-World Integrations¶

Caching: LRU eviction (1D rec on hits).
Genomics: 1D alignment prefixes.
Finance: Daily returns (Fib-like trends).

2D Dynamic Programming¶

2D Dynamic Programming (DP) extends 1D by incorporating two interdependent dimensions in the state space, typically forming a table T[0..N][0..M] where T[i][j] captures the optimal value for subproblems defined by indices i and j (e.g., prefixes of two sequences). This captures interactions like alignments or grid paths, yielding O(N M) time/space but enabling solutions to problems intractable in 1D (e.g., edit distance). Unlike 1D's linear chains, 2D models meshes or matrices with transitions from adjacent cells (up/left/diagonal). Theoretical foundations: Cartesian product states; filling via wavefront (diagonals for dependency).

1. Core Mechanics¶

2D DP solves f(i,j) by filling a table row-by-row or diagonal-by-diagonal, where T[i][j] depends on T[i-1][j], T[i][j-1], T[i-1][j-1] (local window).

State Definition: T[i][j] = optimal for first i of seq1, first j of seq2 (e.g., max alignment score).
Transition: T[i][j] = opt { T[i-1][j] + del(i), T[i][j-1] + ins(j), T[i-1][j-1] + match(i,j) }.
Base Cases: T[0][j]=cost ins 1..j; T[i][0]=cost del 1..i.
Filling Order: Bottom-up: For i=0 to N: For j=0 to M (row-major); or anti-diagonal for space.
Top-Down: Recurse with memo (2D dict/array); prune impossible (e.g., i=0 or j=0).
Bottom-Up: Nested loops; O(1) per cell.

Pseudocode Template (Bottom-Up Row-Major):

function twoD_DP(N: int, M: int, base_row: func(int,int)->val, base_col: func(int,int)->val, trans: func(int,int, array<array<val>>)->val): array<array<val>>
    T = 2D array[N+1][M+1]
    for i from 0 to N:
        T[i][0] = base_col(i, 0)  // e.g., i * del_cost
    for j from 0 to M:
        T[0][j] = base_row(0, j)  // e.g., j * ins_cost
    for i from 1 to N:
        for j from 1 to M:
            T[i][j] = trans(i, j, T)  // e.g., max(T[i-1][j], T[i][j-1], T[i-1][j-1] + match)
    return T

2. Complexity Analysis¶

2D DP's hallmark: O(N M) time/space, with O(1) transitions; scales to N=M=10^3 (10^6 cells).

Time Complexity:

Transition Type Time Derivation

O(1) Local (LCS) O(N M) N M cells × O(1)

O(N+M) Window (Global Align) O(N M (N+M)) Rare; usually local
- Details: Nested loops N M; each O(1) opt. Space O(N M); optimized O(min(N,M)).
Space Complexity:

Variant Space Notes

Full Table O(N M) T[0..N][0..M]

Rolling (2 Rows) O(M) Keep prev/next row

Diagonal O(N + M) For bandwidth-limited
Average/Worst: Dense: O(N M); sparse memo: O(visited ≤N M).

3. Derivations and Theoretical Foundations¶

Recurrence Derivation: From 2D grid: f(i,j) = opt over choices {f(i-1,j) vertical, f(i,j-1) horizontal, f(i-1,j-1) diagonal + cost}.
Wavefront Filling: Dependencies form anti-diagonals (i+j=const); parallel per diagonal.
Quadrangle Inequality: If cost(i,j) + cost(i',j') ≤ cost(i,j') + cost(i',j) (i≤i'≤j≤j'), Knuth-Yao speeds to O(N M / log(N M)) or O(N) convex.

4. Proofs of Correctness and Optimality¶

Induction on (i,j): Lex order (i then j). Base axes correct (1D chains). Inductive: T[i][j] = opt over correct priors + marginal → optimal rectangle [1..i][1..j].
Overlapping Reuse: Each cell once; naive recurse expo (2^{N+M}) → quadratic.
Space Correctness (Rolling): Row i uses only i-1; discard older.

5. Classic 2D Examples¶

Longest Common Subsequence (LCS): Sequence Matching

State: T[i][j] = LCS len of X[1..i], Y[1..j].
Trans: If X[i]==Y[j]: T[i-1][j-1]+1; else max(T[i-1][j], T[i][j-1]).
Base: T[i][0]=T[0][j]=0.
Complexity: O(N M) time/space.

Pseudocode (Bottom-Up):

function lcs(X: string, Y: string): int
    N, M = len(X), len(Y)
    T = 2D array[N+1][M+1] init 0
    for i from 1 to N:
        for j from 1 to M:
            if X[i-1] == Y[j-1]:
                T[i][j] = T[i-1][j-1] + 1
            else:
                T[i][j] = max(T[i-1][j], T[i][j-1])
    return T[N][M]

Edit Distance (Levenshtein): String Alignment
- State: T[i][j] = min ops to align X[1..i], Y[1..j].
- Trans: If match: T[i-1][j-1]; del: T[i-1][j]+1; ins: T[i][j-1]+1; sub: T[i-1][j-1]+(0/1 mismatch).
- Base: T[i][0]=i, T[0][j]=j.
- Complexity: O(N M).
Grid Path Counting/Min Cost: 2D Lattice
- State: T[i][j] = ways/min cost to (i,j) from (0,0) (right/down).
- Trans: T[i][j] = T[i-1][j] + T[i][j-1].
- Base: T[0][0]=1; row/col cumul.

6. Advanced Variants¶

Space-Optimized 2D: Rolling 2 rows (prev/curr); O(M) for N>>M.
- Mechanics: For i=1 to N: Copy prev=row i-1; fill curr[j] from prev[j], curr[j-1], prev[j-1].
Parallel 2D DP: Diagonal wavefront (i+j=const); O(N M / p + N log p).
Convex 2D: For quadrangle (e.g., MCM), divide-conquer O(N log N M).

7. Pros/Cons, Optimizations, and Practical Nuances¶

Pros: Handles 2D interactions (alignments); O(1) cell.
Cons: O(N M) space quadratic; N=M=10^4 =10^8 ok.
Optimizations: Rolling space; bit-parallel for binary (e.g., LCS bits).
Empirical: For N=M=5000, ~1GB/10s; debug slice tables.

8. Applications and Real-World Integrations¶

NLP: LCS for plagiarism; edit for spell-check.
Bio: Sequence alignment (Smith-Waterman local 2D).
Robotics: Grid maps (path cost 2D DP).
Games: Word search (edit variants).

0/1 Knapsack Problem in Dynamic Programming¶

The 0/1 Knapsack problem is a cornerstone of combinatorial optimization, modeling the challenge of selecting a subset of items (each with weight w_i and value v_i) to maximize total value without exceeding knapsack capacity W, where items are indivisible (0/1: take or leave). Formulated as max ∑ v_i x_i s.t. ∑ w_i x_i ≤ W, x_i ∈ {0,1}, it exemplifies NP-hard (pseudo-polynomial via DP) problems with optimal substructure: Optimal for first i items/capacity w = opt of skip or take (if fits). DP transforms exponential 2^n brute force into O(n W) via 2D table T[i][w] = max value using first i items, capacity w. Theoretical ties: Unbounded variant (multiples) via 1D; approximations (PTAS FPTAS O(n log(1/ε))).

1. Core Mechanics¶

0/1 Knapsack DP builds a table where rows = items (i=1..n), columns = capacities (w=0..W), filling bottom-up to avoid recursion expo.

State Definition: T[i][w] = max value using subset of first i items, exact capacity ≤w (or =w for unbounded).
Transition: T[i][w] = max{ T[i-1][w] (skip i), T[i-1][w - w_i] + v_i if w ≥ w_i (take i) }.
Base Cases: T[0][w]=0 ∀w (no items); T[i][0]=0 ∀i (zero capacity).
Filling Order: For i=1 to n: For w=0 to W (forward to avoid reuse in 0/1).
Top-Down: Recurse T(n,W): If memo hit return; else max(skip, take if fits); memo.
Bottom-Up: Nested loops; reconstruct via trace (another table for choices).

Pseudocode Template (Bottom-Up 2D):

function zeroOneKnapsack(n: int, W: int, values: array<int>, weights: array<int>): int
    T = 2D array[n+1][W+1] init 0
    for i from 1 to n:
        for w from 0 to W:
            T[i][w] = T[i-1][w]  // Skip
            if weights[i-1] <= w:
                T[i][w] = max(T[i][w], T[i-1][w - weights[i-1]] + values[i-1])
    return T[n][W]

2. Complexity Analysis¶

0/1 Knapsack's O(n W) is pseudo-polynomial (poly in numeric values, expo in bits), WNP-hard.

Time Complexity:

Variant Time Derivation

Basic 2D O(n W) n rows × W cols × O(1) max

1D Space Opt O(n W) Same; backward fill
- Details: Each cell O(1); total n(W+1) ≈ n W. W=10^5, n=100: 10^7 ops.
Space Complexity:

Variant Space Derivation

2D Full O(n W) Table size

1D Rolling O(W) Single array; prev implicit
- Details: 1D: For i=n downto 1: For w=W downto w_i: T[w] = max(T[w], T[w - w_i] + v_i).
Average/Worst: Uniform w_i: O(n W); adversarial W expo bits.

3. Derivations and Theoretical Foundations¶

Recurrence Derivation: Optimal K(i,w) = max( K(i-1,w) skip, K(i-1,w-w_i)+v_i take ); substructure: Sol for i,w uses sol for i-1,w or i-1,w-w_i.
Pseudo-Poly: Time poly(W), but W=2^{bits} → expo input size.
Unbounded Variant: 1D T[w] = max(T[w], T[w - w_i] + v_i) forward (reuse).

4. Proofs of Correctness and Optimality¶

Induction on i (Items): Base i=0: T[0][w]=0 correct. Inductive: Assume T[i-1][*] optimal; T[i][w] = max over optimal subs (skip/take) + marginal → optimal for i.
On w (Capacity): For fixed i, induct w=0 to W: Bases 0 correct; T[i][w] uses T[i][w'] w'\<w or T[i-1][w/w'] (ind by i or w).
No Reuse in 0/1: Backward fill ensures take uses prior row's w-w_i.

5. Classic Variants and Extensions¶

Unbounded Knapsack: Multiple Items
- State: T[w] = max value ≤w (1D).
- Trans: For each coin i: For w=w_i to W: T[w] = max(T[w], T[w - w_i] + v_i).
- Complexity: O(n W); forward to allow multiples.
Multiple Constraints (MD Knapsack): T[i][w1][w2]... = O(n W1 W2..) expo dims.
Fractional Knapsack: Greedy sort v/w; O(n log n) (not DP).
Reconstruct Sol: Trace T: From T[n][W], if T[n][W] == T[n-1][W] skip n; else take n, recurse T[n-1][W-w_n].

Pseudocode (1D Space Opt):

function zeroOneKnapsack_1D(W: int, values: array<int>, weights: array<int>): int
    n = values.length
    T = array<int>(W + 1, 0)
    for i from 1 to n:
        for w from W downto weights[i-1]:  // Backward for 0/1
            T[w] = max(T[w], T[w - weights[i-1]] + values[i-1])
    return T[W]

6. Advanced Variants¶

FPTAS (Fully Poly-Time Approx Scheme): Scale values to v'/ε, DP O(n (W/ε)); (1-ε)-approx O(n² / ε³).
Parallel Knapsack: Distribute w columns; sync boundaries. O(n W / p + n log p).
Quantum: Grover O(√(2^n)) search, but classical DP better.

7. Pros/Cons, Optimizations, and Practical Nuances¶

Pros: Exact optimal; pseudo-poly practical.
Cons: W large → slow/space; NP-hard no poly.
Optimizations: 1D rolling; prune w if T[w]=T[w-1] (no improvement).
Empirical: n=100, W=10^4: 10^6 ops instant; reconstruct via bitmask or trace.

8. Applications and Real-World Integrations¶

Logistics: Item packing (weights=size, values=priority).
Crypto: Subset sum (v_i=1); attacks on knapsack ciphers.
Resource Alloc: Budget (W=money, w_i=cost).
ML: Feature selection (w_i=complexity).

Problem Type	#States	Transitions/State	Total Time
1D (Fib)	O(n)	O(1)	O(n)
2D (LCS)	O(n m)	O(1)	O(n m)
Knapsack	O(n W)	O(n)	O(n² W)

Transition Type	Time	Derivation
O(1) Opts (Fib)	O(N)	N steps × O(1)
O(N) Opts (Naive LIS)	O(N²)	N × avg N/2

Variant	Space	Notes
Full Table	O(N)	T[0..N]
Sliding Vars	O(1)	Keep last k (e.g., Fib: prev2, prev1)

Transition Type	Time	Derivation
O(1) Local (LCS)	O(N M)	N M cells × O(1)
O(N+M) Window (Global Align)	O(N M (N+M))	Rare; usually local

Variant	Space	Notes
Full Table	O(N M)	T[0..N][0..M]
Rolling (2 Rows)	O(M)	Keep prev/next row
Diagonal	O(N + M)	For bandwidth-limited

Variant	Time	Derivation
Basic 2D	O(n W)	n rows × W cols × O(1) max
1D Space Opt	O(n W)	Same; backward fill

Variant	Space	Derivation
2D Full	O(n W)	Table size
1D Rolling	O(W)	Single array; prev implicit