Dynamic Programming
Open in the Padhaiko app5.1 Basic concepts
Dynamic Programming (DP) solves optimization and counting problems by breaking them into simpler subproblems, storing each subproblem's solution once in a table, and reusing those stored results rather than recomputing them.
Core Principles of Dynamic Programming
A problem is suited for Dynamic Programming when it exhibits two properties:
- Optimal Substructure (Bellman's Principle of Optimality): An optimal solution to the problem is constructed from optimal solutions to its subproblems.
- Overlapping Subproblems: A naive recursive solution solves the same subproblems repeatedly (unlike Divide and Conquer, where subproblems are disjoint).
Four Steps to Design a DP Algorithm:
- Characterize the structure of an optimal solution.
- Recursively define the value of an optimal solution (recurrence + base cases).
- Compute the value of an optimal solution—either bottom-up (tabulation) or top-down with memoization.
- Reconstruct the actual optimal solution from stored choice/parent pointers.
| Aspect | Top-Down (Memoization) | Bottom-Up (Tabulation) |
|---|---|---|
| Execution Order | Recursive from original problem down to base cases | Iterative from smallest base cases up to target size |
| Subproblems Evaluated | Only subproblems actually needed (lazy) | All subproblems in the DP table |
| Overhead | Recursion call-stack overhead | No recursion overhead; better cache locality and easy space reduction |
5.2 All pair shortest path algorithm
The Floyd-Warshall algorithm computes shortest-path distances between every pair of vertices in a weighted directed graph with vertices (negative edge weights allowed, provided there are no negative-weight cycles).
Floyd-Warshall DP Recurrence
Let be the shortest path weight from vertex to vertex using only intermediate vertices from :
- Base case (): ( if , if no direct edge ).
- Recurrence (): Either the path avoids vertex or passes through :
void floydWarshall(int n, int D[n][n]) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (D[i][k] < INF && D[k][j] < INF &&
D[i][k] + D[k][j] < D[i][j]) {
D[i][j] = D[i][k] + D[k][j];
}
}
}
}
}- Time Complexity: Three nested loops of length ().
- Space Complexity: (can overwrite in-place).
- Negative Cycle Detection: After , a negative cycle exists iff for some .
1
Apply the Floyd-Warshall algorithm to compute the all-pairs shortest path matrix for the -vertex directed graph whose initial weight matrix is:
Iterations and :
- (via vertex ): Updates using column () and row ():
- (via vertex ): Using and : , :
Iterations and :
- (via vertex ): , , :
- (via vertex ): , , :
The final all-pairs shortest path matrix is:
5.3 Travelling salesperson problem
Given cities and a cost matrix , the Travelling Salesperson Problem (TSP) seeks a minimum-cost Hamiltonian tour starting at city , visiting every other city exactly once, and returning to city .
Held-Karp Dynamic Programming Formulation for TSP
Let denote the minimum cost of a path starting at city , visiting every city in subset () exactly once, and ending at city :
- Base case (): for each .
- Recurrence ():
- Optimal Tour Cost: .
- Time Complexity: There are states and each transition takes time (vastly faster than brute force, though still exponential since TSP is NP-hard).
- Space Complexity: to store the DP table.
5.4 String editing
The String Editing (Edit Distance / Levenshtein Distance) problem finds the minimum number (or minimum cost) of single-character edit operations—Insertion, Deletion, and Substitution (Replacement)—needed to transform source string into target string .
Edit Distance DP Recurrence
Let be the minimum edit cost to transform prefix into (unit cost per insert, delete, or mismatch substitution; on match):
- Base cases: ( deletions) and ( insertions).
- Recurrence ():
where corresponds to deletion of , to insertion of , and to substitution .
- Time Complexity: ; Space Complexity: (or if only distance is needed).
5.5 0/1 knapsack problem using dynamic programming
Given items with integer weights and values , and integer capacity , each item is either taken () or left ().
0/1 Knapsack DP Recurrence
Let be the maximum value achievable using a subset of the first items within capacity (, ):
- Base cases: and .
- Recurrence:
- Time Complexity: (pseudo-polynomial, because it is polynomial in the numeric capacity rather than the bits encoding ).
- Space Complexity: for full table (needed for backtracking chosen items), or for value only.
5.6 Matrix chain multiplication
Given a chain of matrices where matrix has dimensions , matrix multiplication is associative, yet the parenthesization dramatically changes the total number of scalar multiplications (multiplying a matrix by a matrix takes scalar multiplications).
Matrix Chain Multiplication Recurrence
Let be the minimum scalar multiplications needed to compute ():
- Base case (): .
- Recurrence (): Try every split point :
Record the minimizing split in to reconstruct the optimal parenthesization recursively.
- Time Complexity: subproblems split choices each ; Space Complexity: .
2
Find the minimum number of scalar multiplications and the optimal parenthesization for multiplying matrices with dimension sequence (so ).
Chain lengths and :
- : .
- :
- ()
- ()
- ()
Chain lengths and :
- :
- :
- : .
- :
- :
- : .
- :
- :
- :
- : .
Backtracking splits: ; .
Minimum scalar multiplications , achieved by optimal parenthesization .
5.7 Flow shop scheduling
In Flow Shop Scheduling, jobs must all be processed in the same machine order , where job requires processing time on machine and each machine processes at most one job at a time. The objective is to minimize the makespan (the completion time of the last job on the last machine).
Dynamic Programming Formulation (-Machine / Stage View)
Let denote the minimum total completion time for the remaining job set when machine becomes available units after machine finishes the already-scheduled prefix. By the Principle of Optimality, choosing job next shifts by and leaves busy until after finishes :
Johnson's Algorithm for Two-Machine Flow Shop ()
For machines () with processing times , Johnson's rule finds the globally optimal permutation in time:
- Find the smallest remaining processing time across all unscheduled jobs on both and .
- If the minimum occurs on (), place job as early as possible in the sequence; if it occurs on (), place as late as possible (break ties arbitrarily).
- Remove and repeat until all jobs are scheduled.
3
- Solve the 0/1 Knapsack problem using Dynamic Programming for capacity and items : .
- Compute the String Edit Distance between
CARTandMARCHusing the DP table.
0/1 Knapsack DP table ():
| Item | ||||||
|---|---|---|---|---|---|---|
| (none) | ||||||
| 37 |
Backtracking from : take Item 4 (), remaining . (skip Item 3). : take Item 2 (), remaining . : take Item 1 ().
String Edit Distance DP table (CART MARCH):
M | A | R | C | H | ||
|---|---|---|---|---|---|---|
C | ||||||
A | ||||||
R | ||||||
T | 3 |
Minimum edit distance is (substitute CM, keep A, R, substitute TC, insert H).
- 0/1 Knapsack maximum value (selecting Items with total weight ).
- Edit distance from
CARTtoMARCH.
Exercises
Exercises — Dynamic Programming
Define Optimal Substructure and Overlapping Subproblems in Dynamic Programming, and contrast Memoization with Tabulation (using Fibonacci numbers as an illustration).
Optimal Substructure and Overlapping Subproblems:
- Optimal Substructure: An optimal solution to a problem incorporates optimal solutions to its subproblems (Bellman's Principle of Optimality).
- Overlapping Subproblems: A recursive decomposition visits the exact same subproblems multiple times (e.g., computing calls twice and three times), so storing each subproblem's result eliminates redundant exponential work.
Memoization vs. Tabulation:
- Memoization (Top-Down): Keeps the recursive definition (
fib(n) = fib(n-1) + fib(n-2)) and caches computed values inmemo[n]on first visit. Only needed subproblems are evaluated, but recursion uses stack space. - Tabulation (Bottom-Up): Iteratively fills
dp[0..n]fromdp[0] = 0, dp[1] = 1up todp[n]. Eliminates recursion overhead and allows reducing space from to .
DP applies when a problem has optimal substructure and overlapping subproblems. Memoization caches results top-down inside recursion, whereas tabulation fills the DP table iteratively bottom-up without call-stack overhead.
Solve the Travelling Salesperson Problem (TSP) starting from city using Dynamic Programming (Held-Karp) for the -city directed cost matrix:
Base cases () and single-city subsets ():
- , , .
- :
- ,
- ,
- , .
Two-city subsets () and final tour ():
- (next: )
- (next: )
- (next: )
- (via city ).
Tracing optimal choices: .
Optimal TSP tour: with minimum cost .
Using Dynamic Programming, construct the String Edit Distance table to transform HORSE into ROS (assuming unit cost for insert, delete, and replace) and identify the edit operations.
Constructing the DP table :
R | O | S | ||
|---|---|---|---|---|
H | ||||
O | ||||
R | ||||
S | ||||
E | 3 |
Tracing one optimal sequence of edits:
- Replace
HR(RORSE). - Delete
R(ROSE). - Delete
E(ROS).
Minimum edit distance (replace H with R, delete R, delete E).
Solve the 0/1 Knapsack problem using Dynamic Programming for capacity and items : . Find both the maximum value and the selected subset of items.
Filling the DP table :
- :
- :
- :
- : (at : ).
Backtracking selected items: Since , Item 4 is skipped. Since , Item 3 is taken (remaining ). At , , so Item 2 is taken (remaining ).
Maximum value , obtained by choosing Item 2 and Item 3 (total weight ).
Apply Johnson's algorithm for 2-Machine Flow Shop Scheduling () on the jobs below to find an optimal job sequence and the minimum makespan :
Ordering jobs by Johnson's rule:
- Minimum time is ( on ) place first: .
- Next minimum among is ( on ) place last: .
- Next minimum among is ( on ) place second: .
- Place remaining in slot : optimal sequence is .
Computing completion times and makespan :
- : ; ( waits unit initially).
- : ; .
- : ; .
- : ; .
Total makespan (total time , total time , idle time ).
Optimal job sequence: with minimum makespan .