Dynamic Programming (DP) is an algorithmic paradigm that transforms computationally intractable exponential search spaces into deterministic polynomial-time execution. Coined by mathematician Richard Bellman in the 1950s, dynamic programming applies to problems that exhibit overlapping subproblems and optimal substructure. Rather than recomputing identical sub-solutions through redundant recursive branches, dynamic programming systematically computes, memoizes, and tabulates states along a Directed Acyclic Graph (DAG) of dependencies. Mastering state space formulation, memory compression techniques, and bitmask subset representations is essential for systems engineering, database query optimization, genomics, and operations research.
1. Mathematical Foundations of Dynamic Programming & DAG Transitions#
Dynamic programming is fundamentally about formulating an optimization problem as a sequential decision process over a state space.
The Two Invariants of Dynamic Programming#
A problem can be solved efficiently via dynamic programming if and only if it satisfies two core mathematical properties:
- Optimal Substructure (Bellman's Principle of Optimality):
An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.
In graph-theoretic terms: if the shortest path from vertex A to vertex C passes through vertex B, then the sub-path from A to B must also be the optimal shortest path between A and B. If a sub-path were suboptimal, we could replace it with a shorter sub-path to produce a shorter overall path from A to C, contradicting optimality.
- Overlapping Subproblems:
A naive recursive decomposition of the problem revisits the exact same subproblem states repeatedly, rather than generating unique subproblems at each step.
Consider the standard recursive Fibonacci formulation:
F(n) = F(n - 1) + F(n - 2).
Evaluating F(5) requires computing F(4) and F(3). Evaluating F(4) requires F(3) and F(2). Both branches compute F(3) independently. In general, the naive recursion tree contains 2^n nodes, executing in catastrophic O(2^n) exponential time because identical states are solved millions of times!
+----------------------------------------------------------------------------------------------------+
| EXPONENTIAL RECURSION TREE vs DP DAG |
+----------------------------------------------------------------------------------------------------+
Naive Recursive Tree (O(2^n) Exponential Redundancy):
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1) <-- F(3) and F(2) evaluated multiple times!
/ \
F(2) F(1)
Dynamic Programming State Space (O(n) Directed Acyclic Graph):
[ F(0) ] ---> [ F(1) ] ---> [ F(2) ] ---> [ F(3) ] ---> [ F(4) ] ---> [ F(5) ]
Each state is evaluated exactly once in topological order!
+----------------------------------------------------------------------------------------------------+Contrast with Divide-and-Conquer and Greedy Paradigms#
- Divide-and-Conquer: Partitions the problem into independent, non-overlapping subproblems (e.g., Mergesort, Quicksort). Because subproblems do not share states, memoization provides no benefit.
- Greedy Algorithms: Makes a locally optimal choice at each step without ever backtracking or evaluating alternative branches (e.g., Kruskal's MST, Huffman Coding). Requires the Greedy Choice Property.
- Dynamic Programming: Explores all possible decision branches, but avoids redundant work by memoizing overlapping states.
Top-Down Memoization vs. Bottom-Up Tabulation#
- Top-Down Memoization (Recursive with Caching):
- Preserves the intuitive, natural mathematical recurrence.
- An auxiliary data structure (a hash map or lookup array) is initialized with sentinel values.
- When a recursive function is invoked on state S:
- Check cache: if S is already computed, return the cached result immediately (O(1)).
- If not computed: evaluate the recurrence, store the result in the cache, and return.
- Drawbacks: Function call overhead, stack memory consumption, and the risk of Call Stack Overflow on deep inputs (recursion depth > 10,000 frames).
- Bottom-Up Tabulation (Iterative Evaluation):
- Flattens the recurrence into an iterative loop that fills an n-dimensional table.
- Evaluates subproblems in strict Topological Order along the dependency DAG: base cases are solved first, building progressively toward the target state.
- Advantages: Zero function call overhead, completely immune to stack overflow, highly friendly to CPU cache line prefetching, and enables State Space Compression to reduce physical memory consumption from O(N^2) to O(N) or O(1).
2. Classical 1D & 2D Dynamic Programming Formulations#
Mastering dynamic programming requires recognizing standard canonical state representations.
The 0/1 Knapsack Problem & Pseudo-Polynomial Complexity#
Given n items, where each item i has a positive integer weight w_i and positive integer value v_i, and a knapsack with maximum weight capacity W: select a subset of items to maximize total value such that the total weight does not exceed W. Each item can be chosen at most once (0/1 choice).
State Space Formulation:
Let dp[i][w] denote the maximum value achievable considering a subset of the first i items with a remaining weight capacity budget w (where 0 <= i <= n and 0 <= w <= W).
Base Cases:
dp[0][w] = 0for all w in { 0, 1, ..., W } (0 items yield 0 value).dp[i][0] = 0for all i in { 0, 1, ..., n } (0 capacity holds 0 value).
The Decision Recurrence:
For each item i (with weight w_i and value v_i):
- Exclude Item i: The capacity remains w, and the value is whatever was achieved using the first i - 1 items:
dp[i - 1][w]. - Include Item i (only valid if w_i <= w): The capacity drops to w - w_i, and we gain value v_i:
dp[i - 1][w - w_i] + v_i.
Combine decisions via maximization:
dp[i][w] = dp[i - 1][w] if w_i > w
dp[i][w] = max( dp[i - 1][w], dp[i - 1][w - w_i] + v_i ) if w_i <= w.
Complexity Analysis:
- Table dimensions: (n + 1) × (W + 1).
- Time Complexity: O(n · W).
- Space Complexity: O(n · W).
The Pseudo-Polynomial Nuance:
Is O(n · W) polynomial time?
In computational complexity theory, an algorithm's complexity is measured relative to the number of bits required to encode the input.
An integer W requires k = ceil(log2 W) bits to represent.
Therefore, W = 2^k.
In terms of input bit-length k, the runtime is:
Time = O(n · 2^k).
Because the runtime scales exponentially with the bit-length of W, 0/1 Knapsack is NP-Complete, and its DP algorithm runs in Pseudo-Polynomial Time. If W is small (e.g., W = 10,000), it runs in milliseconds; if W is a 64-bit cryptographic integer (W = 10^18), the DP table would require billions of gigabytes of RAM!
Longest Common Subsequence (LCS)#
Given two strings S1 of length m and S2 of length n: find the length of the longest subsequence present in both strings (characters need not be contiguous, but must preserve relative order).
State Formulation:
Let dp[i][j] be the length of the LCS of prefixes S1[0 ... i - 1] and S2[0 ... j - 1].
Recurrence:
- If S1[i - 1] == S2[j - 1]:
The characters match! Extend the LCS:
dp[i][j] = 1 + dp[i - 1][j - 1].
- If S1[i - 1] != S2[j - 1]:
The characters do not match. The optimal LCS must come from either dropping the last character of S1 or dropping the last character of S2:
dp[i][j] = max( dp[i - 1][j], dp[i][j - 1] ).
Base Cases:
dp[0][j] = 0 and dp[i][0] = 0.
Industrial Application:
The LCS dynamic programming algorithm is the mathematical core of the GNU Diff utility and Git Merge / Rebase conflict resolution engines (specifically, Eugene Myers' O(ND) difference algorithm).
3. State Space Compression: Memory Optimization in Physical RAM#
A common limitation of dynamic programming in production systems is memory consumption. A 2D table of size 50,000 × 50,000 32-bit integers requires 10 Gigabytes of RAM, exceeding typical process limits.
The 1D Rolling Array Compression Principle#
Inspect the 0/1 Knapsack recurrence carefully:
dp[i][w] = max( dp[i - 1][w], dp[i - 1][w - w_i] + v_i ).
Crucial Observation:
To compute any value in row i, the algorithm reads ONLY from row i - 1!
It never references row i - 2, row i - 3, or any earlier history.
Therefore, storing all n rows in memory simultaneously is completely unnecessary!
Can we collapse the entire 2D table into a single 1D array dp[w] of size W + 1?
+----------------------------------------------------------------------------------------------------+
| 1D KNAPSACK REVERSE ITERATION INVARIANT |
+----------------------------------------------------------------------------------------------------+
1D Array: dp[0 ... W]
FORWARD ITERATION (Buggy for 0/1! Correct for Unbounded!):
w = w_i ---> W:
When computing dp[w], it references dp[w - w_i].
Because w - w_i was ALREADY UPDATED earlier in this same loop, it contains item i!
Result: Item i can be selected infinitely many times! (Transforms into Unbounded Knapsack).
REVERSE ITERATION (Strictly Required for 0/1 Knapsack!):
w = W down to w_i:
When computing dp[w], it references dp[w - w_i].
Because w - w_i has NOT YET BEEN UPDATED in this loop, it still holds the value from row i - 1!
Result: Each item i is guaranteed to be used AT MOST ONCE.
+----------------------------------------------------------------------------------------------------+The 1D Compressed Algorithm:
# 1D Compressed 0/1 Knapsack
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1): # REVERSE DIRECTION!
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])Memory complexity drops from O(n · W) to O(W)—an immense reduction from gigabytes to kilobytes!
Hirschberg's Divide-and-Conquer Algorithm (Linear Space Reconstruction)#
What if we need to reconstruct the actual optimal sequence of items or characters (not just the maximum number)?
Space compression retains only the final row, losing the backtracking pointers.
Dan Hirschberg (1975) solved this dilemma by combining dynamic programming with divide-and-conquer:
- By running forward DP on the first half of string S1 and backward DP on the second half of S1, the algorithm finds the exact midpoint where the optimal LCS crosses the middle column.
- It recurses on the two sub-problems.
- Hirschberg's algorithm recovers the complete optimal string in O(m · n) time and strictly O(m + n) memory!
4. Advanced Bitmask Dynamic Programming & Combinatorial State Spaces#
When an optimization problem requires tracking subsets of elements, representing sets as boolean arrays or hash sets is too slow and memory-intensive. Bitmask Dynamic Programming encodes finite combinatorial subsets into the binary bit patterns of machine integers.
The Bitwise Representation of Subsets#
Let a universe consist of n distinct elements labeled 0, 1, 2, ..., n - 1.
Any subset S can be represented uniquely as an integer mask in the range [0, 2^n - 1]:
- Bit i of
maskis 1 if element i is in the subset. - Bit i of
maskis 0 if element i is absent.
Subset of 5 elements: { 0, 2, 3 }
Binary representation: 0 1 1 0 1 (binary) = 13 (decimal)
Bit 0 = 1 (Present), Bit 1 = 0 (Absent), Bit 2 = 1 (Present), Bit 3 = 1 (Present), Bit 4 = 0 (Absent).Fundamental Bitwise Operations:
- Test Membership:
is_present = (mask & (1 << i)) != 0 - Add Element i:
new_mask = mask | (1 << i) - Remove Element i:
new_mask = mask & ~(1 << i) - Toggle Element i:
new_mask = mask ^ (1 << i) - Total Elements in Subset:
count = __builtin_popcount(mask)(1 CPU cycle via POPCNT instruction).
The Traveling Salesperson Problem (TSP) via the Held-Karp Algorithm#
Given n cities and a distance matrix dist[u][v], find the minimum cost tour that starts at city 0, visits every city exactly once, and returns to city 0.
Brute-force permutation search tests (n - 1)! paths.
For n = 20 cities:
19! ≈ 1.21 × 10^17 operations (would run for decades!).
The Held-Karp Bitmask DP Formulation (1962):
Define State:
dp[mask][u] = The minimum cost to visit all cities represented by the set mask, starting at city 0 and currently ending at city u (where u in mask).
Base Case:
dp[1 << 0][0] = 0 (starting at city 0 with mask containing only city 0 costs 0).
All other states initialized to infinity.
Recurrence Relation:
To reach state (mask, u), the salesperson must have previously visited subset mask \ {u} and ended at some intermediate city v (where v in mask and v ≠ u), and then traveled along edge (v, u):
dp[mask][u] = min_{v in mask, v != u} [ dp[mask & ~(1 << u)][v] + dist[v][u] ].
Final Tour Completion:
Once all cities have been visited (when mask == (1 << n) - 1), add the cost to return from the final city u back to the starting city 0:
Optimal_Cost = min_{u = 1 ... n-1} [ dp[(1 << n) - 1][u] + dist[u][0] ].
Complexity Analysis:
- Total masks: 2^n.
- Cities per mask: n.
- Total states: n · 2^n.
- Work per state: n transitions.
- Total Runtime: O(n^2 · 2^n).
- Space Complexity: O(n · 2^n).
For n = 20 cities:
n^2 · 2^n = (400) · (1,048,576) ≈ 4.19 × 10^8 operations (runs in ~0.2 seconds on a modern CPU!).
Bitmask DP transforms an impossible factorial problem into a tractable, production-grade algorithm.
Efficient Submask Iteration in O(3^n)#
A common requirement in bitmask DP is iterating over all valid submasks of a given mask:
// Enumerating all submasks of a mask efficiently
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
// Process submask
}The expression (submask - 1) & mask automatically steps to the next valid submask, skipping millions of irrelevant integers.
Summing over all masks of size n:
Total Submask Operations = ∑_{k=0}^n [ binom(n, k) · 2^k ] = (1 + 2)^n = 3^n.
This is dramatically faster than the naive O(4^n) loop!
5. Production Systems & Low-Level Architectural Applications#
Dynamic programming operates at the core of industrial search engines, telecommunications, and financial trading.
Regular Expression Engines: Thompson NFA vs. DP Backtracking#
In modern web applications, vulnerable regex engines (e.g., standard PCRE, Python re, JavaScript RegExp) use recursive backtracking. On inputs like "a?^n a^n" matching "a"^n, backtracking takes O(2^n) time, enabling ReDoS (Regular Expression Denial of Service) attacks that freeze web servers.
Google's production regex engine, RE2, implements Ken Thompson's dynamic programming NFA simulation:
- It tracks all active NFA states simultaneously using a rolling bitset.
- Transitioning across characters takes strictly O(n · |regex|) time and O(|regex|) space.
- RE2 provides a mathematical guarantee against exponential blowups, making public regex processing 100% immune to ReDoS attacks.
High-Frequency Trading Limit Order Execution#
In quantitative finance, institutional trading desks execute multi-million-dollar stock orders over time using the Almgren-Chriss Optimal Execution Framework:
- Selling 1,000,000 shares instantly crashes the market price (Market Impact Cost).
- Spreading the sale over 5 hours exposes the portfolio to price volatility risk (Timing Risk).
- Quantitative firms formulate the problem as a dynamic program over discrete time steps t: balancing market impact against price variance to calculate the exact optimal liquidation trajectory on the microsecond scale.
6. Common Pitfalls & Antipatterns in Dynamic Programming#
Engineers frequently encounter insidious bugs when formulating DP solutions.
Pitfall 1: False Assumptions of Optimal Substructure#
A widespread fallacy is assuming every optimization problem has optimal substructure:
- Shortest Path has optimal substructure: sub-paths of shortest paths are shortest paths.
- Longest Simple Path DOES NOT have optimal substructure!
Consider vertices A -> B -> C -> D. The longest simple path from A to D might be A -> B -> C -> D. But the longest simple path from A to B might be A -> C -> D -> B.
Notice that the sub-path A -> C -> D -> B uses vertices C and D, which cannot be reused to continue to D without creating a cycle!
Because remaining choices depend on the historical path taken, the subproblems are NOT independent. Consequently, Longest Simple Path is NP-Hard!
Pitfall 2: Iterating Capacity in the Wrong Direction in 1D Knapsack#
As proven in Section 3:
- Reverse Loop (
wfromWdown tow_i): Solves 0/1 Knapsack (items used at most once). - Forward Loop (
wfromw_iup toW): Solves Unbounded Knapsack (items can be reused infinitely).
Switching the loop direction silently corrupts the mathematical constraints without triggering any syntax or compiler errors!
Pitfall 3: 64-Bit Integer Overflow in Counting DP#
In combinatorial counting problems (e.g., counting paths in a grid or parsing valid parenthesizations via Catalan numbers):
Values grow exponentially. By step n = 65, the count exceeds 2^63 - 1, causing silent integer overflow and wrap-around into negative numbers in C/C++/Java. Always compute states modulo a large prime (e.g., modulo 1,000,000,007) or use arbitrary-precision arithmetic (BigInteger).
7. Comprehensive Checkpoint Practice Problems & Complete Step-by-Step Solutions#
Mastery of dynamic programming, space compression, and bitmask optimization requires solving rigorous quantitative trace problems.
Problem 1 (0/1 Knapsack 2D-to-1D Space Compression & Item Reconstruction):
An aerospace payload manager selects equipment items for an autonomous orbital satellite.
The payload bay has a maximum weight capacity of W = 8 kg.
There are n = 4 candidate equipment items available:
- Item 0: Weight w0 = 2 kg, Value v0 = 3
- Item 1: Weight w1 = 3 kg, Value v1 = 4
- Item 2: Weight w2 = 4 kg, Value v2 = 5
- Item 3: Weight w3 = 5 kg, Value v3 = 8
- Trace the execution of the 1D compressed dynamic programming array
dp[w](for w = 0 to 8) as each of the 4 items is processed sequentially in reverse capacity order. Show the complete array state after each item is processed. - Determine the optimal total value achievable.
- Reconstruct the exact subset of items selected to achieve this maximum value, and verify that total weight <= 8 kg.
Solution:
Step 1: 1D Array Execution Trace
Initialize 1D array of size W + 1 = 9 with zeroes:
Initial: dp = [ 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
- Processing Item 0 (w0 = 2, v0 = 3):
Loop w from 8 down to 2:
dp[w] = max(dp[w], dp[w - 2] + 3).
- w = 8: max(0, dp[6] + 3) = 3
- w = 7: max(0, dp[5] + 3) = 3
- w = 6: max(0, dp[4] + 3) = 3
- w = 5: max(0, dp[3] + 3) = 3
- w = 4: max(0, dp[2] + 3) = 3
- w = 3: max(0, dp[1] + 3) = 3
- w = 2: max(0, dp[0] + 3) = 3
State after Item 0:
dp = [ 0, 0, 3, 3, 3, 3, 3, 3, 3 ]
- Processing Item 1 (w1 = 3, v1 = 4):
Loop w from 8 down to 3:
dp[w] = max(dp[w], dp[w - 3] + 4).
- w = 8: max(dp[8], dp[5] + 4) = max(3, 3 + 4) = 7
- w = 7: max(dp[7], dp[4] + 4) = max(3, 3 + 4) = 7
- w = 6: max(dp[6], dp[3] + 4) = max(3, 3 + 4) = 7
- w = 5: max(dp[5], dp[2] + 4) = max(3, 3 + 4) = 7
- w = 4: max(dp[4], dp[1] + 4) = max(3, 0 + 4) = 4
- w = 3: max(dp[3], dp[0] + 4) = max(3, 0 + 4) = 4
State after Item 1:
dp = [ 0, 0, 3, 4, 4, 7, 7, 7, 7 ]
- Processing Item 2 (w2 = 4, v2 = 5):
Loop w from 8 down to 4:
dp[w] = max(dp[w], dp[w - 4] + 5).
- w = 8: max(dp[8], dp[4] + 5) = max(7, 4 + 5) = 9
- w = 7: max(dp[7], dp[3] + 5) = max(7, 4 + 5) = 9
- w = 6: max(dp[6], dp[2] + 5) = max(7, 3 + 5) = 8
- w = 5: max(dp[5], dp[1] + 5) = max(7, 0 + 5) = 7
- w = 4: max(dp[4], dp[0] + 5) = max(4, 0 + 5) = 5
State after Item 2:
dp = [ 0, 0, 3, 4, 5, 7, 8, 9, 9 ]
- Processing Item 3 (w3 = 5, v3 = 8):
Loop w from 8 down to 5:
dp[w] = max(dp[w], dp[w - 5] + 8).
- w = 8: max(dp[8], dp[3] + 8) = max(9, 4 + 8) = 12!
- w = 7: max(dp[7], dp[2] + 8) = max(9, 3 + 8) = 11!
- w = 6: max(dp[6], dp[1] + 8) = max(8, 0 + 8) = 8
- w = 5: max(dp[5], dp[0] + 8) = max(7, 0 + 8) = 8!
State after Item 3:
dp = [ 0, 0, 3, 4, 5, 8, 8, 11, 12 ]
Step 2: Optimal Value
The maximum value achievable with total weight <= 8 kg is:
dp[8] = 12.
Step 3: Item Reconstruction
Backtrack through the decision history:
- At Item 3 (w = 5, v = 8):
Did dp[8] change from row 2?
In row 2, dp[8] was 9. In row 3, dp[8] became 12 (since dp[3] + 8 = 4 + 8 = 12).
Therefore, Item 3 WAS SELECTED!
Remaining capacity = 8 - 5 = 3 kg.
- At Item 2 (w = 4, v = 5):
Remaining capacity is 3 kg. Since w2 = 4 > 3, Item 2 cannot fit.
Item 2 was NOT selected.
- At Item 1 (w = 3, v = 4):
At capacity 3, row 1 had dp[3] = 4. Row 0 had dp[3] = 3.
Since dp[0] + 4 = 0 + 4 = 4 == dp[3], Item 1 WAS SELECTED!
Remaining capacity = 3 - 3 = 0 kg.
- At Item 0 (w = 2, v = 3):
Remaining capacity is 0 kg. Item 0 was NOT selected.
Selected Items: { Item 1, Item 3 }.
Verification:
- Total Weight = w1 + w3 = 3 kg + 5 kg = 8 kg <= 8 kg (Legal!).
- Total Value = v1 + v3 = 4 + 8 = 12 (Matches optimal value!).
Problem 2 (Longest Common Subsequence Table Construction & Backtracking):
Two DNA sequence fragments are analyzed for evolutionary homology:
- Sequence 1:
S1 = "AGGTAB"(length m = 6) - Sequence 2:
S2 = "GXTXAYB"(length n = 7)
- Construct the complete 7 × 8 Dynamic Programming table
dp[i][j]computing the length of the Longest Common Subsequence. - State the numerical length of the LCS.
- Trace the backtracking path from cell
dp[6][7]back todp[0][0]and output the exact homologous LCS string.
Solution:
Step 1: Construct the DP Table
Table rows correspond to S1 (indices 0 to 6), columns correspond to S2 (indices 0 to 7):
Base row 0 and column 0 are all zeroes.
Recurrence:
If S1[i-1] == S2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Compute row by row:
"" G X T X A Y B
"" [ 0, 0, 0, 0, 0, 0, 0, 0 ]
A A [ 0, 0, 0, 0, 0, 1, 1, 1 ]
G G [ 0, 1, 1, 1, 1, 1, 1, 1 ]
G G [ 0, 1, 1, 1, 1, 1, 1, 1 ]
T T [ 0, 1, 1, 2, 2, 2, 2, 2 ]
A A [ 0, 1, 1, 2, 2, 3, 3, 3 ]
B B [ 0, 1, 1, 2, 2, 3, 3, 4 ]Detailed Walkthrough of Key Matches:
- Row 1 ('A'): Matches 'A' at col 5 ->
dp[1][5] = 1 + dp[0][4] = 1. - Row 2 ('G'): Matches 'G' at col 1 ->
dp[2][1] = 1 + dp[1][0] = 1. - Row 4 ('T'): Matches 'T' at col 3 ->
dp[4][3] = 1 + dp[3][2] = 1 + 1 = 2. - Row 5 ('A'): Matches 'A' at col 5 ->
dp[5][5] = 1 + dp[4][4] = 1 + 2 = 3. - Row 6 ('B'): Matches 'B' at col 7 ->
dp[6][7] = 1 + dp[5][6] = 1 + 3 = 4.
Step 2: Length of LCS
The value at dp[6][7] is 4.
The Longest Common Subsequence has length 4.
Step 3: Backtracking Trace
Start at cell (i=6, j=7):
- i=6 ('B'), j=7 ('B'): Characters MATCH!
Add 'B' to LCS. Move diagonally to (5, 6).
- i=5 ('A'), j=6 ('Y'): Mismatch.
dp[4][6] = 2, dp[5][5] = 3.
Max comes from left (5, 5). Move left to (5, 5).
- i=5 ('A'), j=5 ('A'): Characters MATCH!
Add 'A' to LCS. Move diagonally to (4, 4).
- i=4 ('T'), j=4 ('X'): Mismatch.
dp[3][4] = 1, dp[4][3] = 2.
Max comes from left (4, 3). Move left to (4, 3).
- i=4 ('T'), j=3 ('T'): Characters MATCH!
Add 'T' to LCS. Move diagonally to (3, 2).
- i=3 ('G'), j=2 ('X'): Mismatch.
dp[2][2] = 1, dp[3][1] = 1.
Move up to (2, 2).
- i=2 ('G'), j=2 ('X'): Mismatch.
Move left to (2, 1).
- i=2 ('G'), j=1 ('G'): Characters MATCH!
Add 'G' to LCS. Move diagonally to (1, 0).
- Reached border (j=0). Terminate!
Reconstruct collected characters in reverse order:
Matches collected: 'B', 'A', 'T', 'G'.
Reversed order: "GTAB".
Verification:
- In S1 ("AGGTAB"): A-G-G-T-A-B (Contains "GTAB").
- In S2 ("GXTXAYB"): G-X-T-X-A-Y-B (Contains "GTAB").
Length = 4 characters.
Problem 3 (Held-Karp Bitmask TSP State Trace on a 4-City Network):
A delivery drone must visit N = 4 cities labeled 0, 1, 2, 3.
The symmetric distance matrix between cities is:
City 0 City 1 City 2 City 3
City 0 [ 0, 10, 15, 20 ]
City 1 [ 10, 0, 35, 25 ]
City 2 [ 15, 35, 0, 30 ]
City 3 [ 20, 25, 30, 0 ]The drone starts and ends at City 0.
Subsets of visited cities are encoded as 4-bit binary masks:
- Bit 0 = City 0, Bit 1 = City 1, Bit 2 = City 2, Bit 3 = City 3.
- State the base case initialization for
dp[mask][u]. - Compute all valid DP states for subsets of size 2 (containing City 0 and one other city).
- Compute all valid DP states for subsets of size 3.
- Compute the final state for mask = 15 (
1111in binary, all 4 cities visited) and determine the exact optimal tour cost and routing order.
Solution:
Step 1: Base Case Initialization
The drone starts at City 0.
Mask containing only City 0 is 1 << 0 = 1 (0001 binary).
dp[1][0] = 0.
All other dp[mask][u] = ∞.
Step 2: Subsets of Size 2 (Masks with 2 bits set, including bit 0)
- Mask = 3 (
0011binary: { City 0, City 1 }):
Must end at City 1 (u = 1):
dp[3][1] = dp[1][0] + dist[0][1] = 0 + 10 = 10.
- Mask = 5 (
0101binary: { City 0, City 2 }):
Must end at City 2 (u = 2):
dp[5][2] = dp[1][0] + dist[0][2] = 0 + 15 = 15.
- Mask = 9 (
1001binary: { City 0, City 3 }):
Must end at City 3 (u = 3):
dp[9][3] = dp[1][0] + dist[0][3] = 0 + 20 = 20.
Step 3: Subsets of Size 3 (Masks with 3 bits set, including bit 0)
- Mask = 7 (
0111binary: { City 0, City 1, City 2 }):
- End at City 1 (u = 1): Came from City 2 with prior mask {0, 2} (mask 5):
dp[7][1] = dp[5][2] + dist[2][1] = 15 + 35 = 50.
- End at City 2 (u = 2): Came from City 1 with prior mask {0, 1} (mask 3):
dp[7][2] = dp[3][1] + dist[1][2] = 10 + 35 = 45.
- Mask = 11 (
1011binary: { City 0, City 1, City 3 }):
- End at City 1 (u = 1): Came from City 3 with prior mask {0, 3} (mask 9):
dp[11][1] = dp[9][3] + dist[3][1] = 20 + 25 = 45.
- End at City 3 (u = 3): Came from City 1 with prior mask {0, 1} (mask 3):
dp[11][3] = dp[3][1] + dist[1][3] = 10 + 25 = 35.
- Mask = 13 (
1101binary: { City 0, City 2, City 3 }):
- End at City 2 (u = 2): Came from City 3 with prior mask {0, 3} (mask 9):
dp[13][2] = dp[9][3] + dist[3][2] = 20 + 30 = 50.
- End at City 3 (u = 3): Came from City 2 with prior mask {0, 2} (mask 5):
dp[13][3] = dp[5][2] + dist[2][3] = 15 + 30 = 45.
Step 4: Subsets of Size 4 (Mask = 15, `1111` binary: All Cities Visited)
Compute dp[15][u] for u in { 1, 2, 3 }:
- End at City 1 (u = 1, prior mask {0, 2, 3} = 13):
- From v = 2: dp[13][2] + dist[2][1] = 50 + 35 = 85.
- From v = 3: dp[13][3] + dist[3][1] = 45 + 25 = 70.
dp[15][1] = min(85, 70) = 70 (Route ended: 0 -> 2 -> 3 -> 1).
- End at City 2 (u = 2, prior mask {0, 1, 3} = 11):
- From v = 1: dp[11][1] + dist[1][2] = 45 + 35 = 80.
- From v = 3: dp[11][3] + dist[3][2] = 35 + 30 = 65.
dp[15][2] = min(80, 65) = 65 (Route ended: 0 -> 1 -> 3 -> 2).
- End at City 3 (u = 3, prior mask {0, 1, 2} = 7):
- From v = 1: dp[7][1] + dist[1][3] = 50 + 25 = 75.
- From v = 2: dp[7][2] + dist[2][3] = 45 + 30 = 75.
dp[15][3] = min(75, 75) = 75.
Step 5: Return to Origin (City 0) & Optimal Tour Selection
Add the cost to return from city u back to City 0 (dist[u][0]):
- Return from City 1:
dp[15][1] + dist[1][0] = 70 + 10 = 80. - Return from City 2:
dp[15][2] + dist[2][0] = 65 + 15 = 80. - Return from City 3:
dp[15][3] + dist[3][0] = 75 + 20 = 95.
Minimum Tour Cost = 80.
Optimal Tour Route Reconstruction:
Achieved via dp[15][2] + dist[2][0]:
Final leg is City 2 -> City 0.
dp[15][2] came from v = 3 (dp[11][3] + dist[3][2]). Leg: City 3 -> City 2.
dp[11][3] came from v = 1 (dp[3][1] + dist[1][3]). Leg: City 1 -> City 3.
dp[3][1] came from City 0. Leg: City 0 -> City 1.
Optimal Tour:
City 0 -> City 1 -> City 3 -> City 2 -> City 0.
Cost verification:
10 (0->1) + 25 (1->3) + 30 (3->2) + 15 (2->0) = 10 + 25 + 30 + 15 = 80.
Problem 4 (Submask Enumeration Combinatorial Complexity Proof):
In advanced bitmask dynamic programming, an algorithm iterates over all submasks S' of every mask S of size n:
for (int mask = 0; mask < (1 << n); mask++) {
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
// Evaluate DP transition
}
}- Using the Binomial Theorem, derive the exact total number of iterations executed by the inner loop across all possible masks of size n.
- Calculate the exact numerical number of operations for n = 10 and n = 20.
- Contrast this with the naive approach of looping through all 2^n numbers for every mask (O(4^n)), and calculate the speedup factor for n = 20.
Solution:
Step 1: Binomial Theorem Summation Proof
Consider an n-element universe.
- For any integer k (where 0 <= k <= n), how many masks contain exactly k set bits (k elements)?
By combinatorics, the number of masks with k set bits is given by the binomial coefficient:
Number_of_Masks(k) = binom(n, k).
- For a mask that contains exactly k set bits, how many submasks can be formed from those k elements?
Every element in the mask can either be included or excluded from the submask.
Therefore, a mask with k bits has exactly 2^k possible submasks:
Submasks_Per_Mask(k) = 2^k.
- Summing over all possible values of k from 0 to n:
Total_Iterations = ∑_{k=0}^n [ binom(n, k) · 2^k ].
Recall the Binomial Theorem:
(x + y)^n = ∑_{k=0}^n [ binom(n, k) · x^{n - k} · y^k ].
Substitute x = 1 and y = 2:
(1 + 2)^n = ∑_{k=0}^n [ binom(n, k) · 1^{n - k} · 2^k ] = ∑_{k=0}^n [ binom(n, k) · 2^k ].
Therefore:
Total_Iterations = (1 + 2)^n = 3^n.
The exact total number of inner loop iterations across all masks is strictly 3^n.
Step 2: Numerical Evaluations
- For n = 10 elements:
Total Iterations = 3^10 = 59,049 operations.
- For n = 20 elements:
Total Iterations = 3^20 = 3,486,784,401 operations (~3.49 × 10^9 operations).
Step 3: Comparison with Naive O(4^n) Approach
In a naive implementation:
- Outer loop tests 2^n masks.
- Inner loop tests all 2^n possible candidates to check if
(candidate & mask) == candidate.
Total Naive Iterations = 2^n · 2^n = (2^2)^n = 4^n.
For n = 20:
- Naive Iterations = 4^20 = 2^40 = 1,099,511,627,776 operations (~1.10 × 10^12 operations).
- Optimized Submask Enumeration = 3^20 = 3,486,784,401 operations.
Speedup Factor:
Speedup = 4^20 / 3^20 = (4 / 3)^20 ≈ (1.33333)^20 ≈ 315.4×.
The submask enumeration trick is over 315 times faster for n = 20, transforming a multi-hour computation into a few seconds of execution!