PadhaikoAll subjects

Dynamic Programming

Analysis of Algorithms (ENCT 388)

Open in the Padhaiko app

5.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.

Definition

Core Principles of Dynamic Programming

A problem is suited for Dynamic Programming when it exhibits two properties:

  1. Optimal Substructure (Bellman's Principle of Optimality): An optimal solution to the problem is constructed from optimal solutions to its subproblems.
  2. 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:

  1. Characterize the structure of an optimal solution.
  2. Recursively define the value of an optimal solution (recurrence + base cases).
  3. Compute the value of an optimal solution—either bottom-up (tabulation) or top-down with memoization.
  4. Reconstruct the actual optimal solution from stored choice/parent pointers.
AspectTop-Down (Memoization)Bottom-Up (Tabulation)
Execution OrderRecursive from original problem down to base casesIterative from smallest base cases up to target size
Subproblems EvaluatedOnly subproblems actually needed (lazy)All subproblems in the DP table
OverheadRecursion call-stack overheadNo 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).

Definition

Floyd-Warshall DP Recurrence

Let be the shortest path weight from vertex to vertex using only intermediate vertices from :

Floyd-Warshall All-Pairs Shortest PathC
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];
                }
            }
        }
    }
}
Example 1

1 (7 marks)

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 ): , , :
Answer:

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 .

Definition

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 :


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 .

Definition

Edit Distance DP Recurrence

Let be the minimum edit cost to transform prefix into (unit cost per insert, delete, or mismatch substitution; on match):

where corresponds to deletion of , to insertion of , and to substitution .


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 ().

Definition

0/1 Knapsack DP Recurrence

Let be the maximum value achievable using a subset of the first items within capacity (, ):


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).

Definition

Matrix Chain Multiplication Recurrence

Let be the minimum scalar multiplications needed to compute ():

Record the minimizing split in to reconstruct the optimal parenthesization recursively.

Example 2

2 (8 marks)

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: ; .

Answer:

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:

  1. Find the smallest remaining processing time across all unscheduled jobs on both and .
  2. 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).
  3. Remove and repeat until all jobs are scheduled.
Example 3

3 (7 marks)

  1. Solve the 0/1 Knapsack problem using Dynamic Programming for capacity and items : .
  2. Compute the String Edit Distance between CART and MARCH using the DP table.

0/1 Knapsack DP table ():

0/1 Knapsack DP Table K[i][w]
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):

Edit Distance Table E[i][j]
MARCH
C
A
R
T3

Minimum edit distance is (substitute CM, keep A, R, substitute TC, insert H).

Answer:
  1. 0/1 Knapsack maximum value (selecting Items with total weight ).
  2. Edit distance from CART to MARCH .

Exercises

Exercises — Dynamic Programming

Question 1

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 in memo[n] on first visit. Only needed subproblems are evaluated, but recursion uses stack space.
  • Tabulation (Bottom-Up): Iteratively fills dp[0..n] from dp[0] = 0, dp[1] = 1 up to dp[n]. Eliminates recursion overhead and allows reducing space from to .
Answer:

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.

Question 2

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: .

Answer:

Optimal TSP tour: with minimum cost .

Question 3

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 :

Edit Distance DP Table for HORSE to ROS
ROS
H
O
R
S
E3

Tracing one optimal sequence of edits:

  1. Replace H R (RORSE).
  2. Delete R (ROSE).
  3. Delete E (ROS).
Answer:

Minimum edit distance (replace H with R, delete R, delete E).

Question 4

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 ).

Answer:

Maximum value , obtained by choosing Item 2 and Item 3 (total weight ).

Question 5

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:

  1. Minimum time is ( on ) place first: .
  2. Next minimum among is ( on ) place last: .
  3. Next minimum among is ( on ) place second: .
  4. Place remaining in slot : optimal sequence is .

Computing completion times and makespan :

  • : ; ( waits unit initially).
  • : ; .
  • : ; .
  • : ; .

Total makespan (total time , total time , idle time ).

Answer:

Optimal job sequence: with minimum makespan .

← Greedy AlgorithmsBacktracking Techniques →