ALGORITHM DESIGN & ANALYSIS

Module 4

Dynamic Programming
30 Hours · Theory & Practice

Topics: Principles of DP · Knapsack Problem · LCS · Matrix Chain Multiplication

Computer Science Department

Module 4 Overview — Dynamic Programming

What You Will Learn in 30 Hours

Principles of DP Knapsack Problem

01 Optimal substructure, overlapping subproblems, 02 0/1 Knapsack, Fractional Knapsack, Space optimization
memoization vs tabulation techniques

Longest Common Subsequence Matrix Chain Multiplication

03 04
LCS algorithm, reconstruction, string similarity applications Optimal parenthesization, MCM DP table, cost analysis
 SECTION 01

Principles of Dynamic Programming

The foundation of all DP algorithms

What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique that solves complex problems by breaking them into simpler
overlapping subproblems and storing their results to avoid redundant computation.

Coined by Core Idea

Richard Bellman, 1950s Solve each sub-problem once

"Programming" = planning, not coding Store results (memoize/tabulate)

Time Saving Key Difference

Exponential → Polynomial vs Divide & Conquer:

Fibonacci: O(2ⁿ) → O(n) Subproblems OVERLAP in DP
Two Essential Properties for DP

1. Optimal Substructure 2. Overlapping Subproblems

An optimal solution to a problem contains optimal The same subproblems are solved repeatedly in a naive
solutions to its subproblems. recursive approach.

Example: Shortest Path Fibonacci Tree (overlap):

If shortest path A→C goes through B, fib(5)

/ \
then A→B must also be shortest.
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
✓ Fibonacci ✓ Knapsack ← fib(3) computed TWICE!
✓ LCS ✓ MCM

Without DP: O(2ⁿ) With DP: O(n)

Problems WITH this property can use DP!
DP Approaches: Memoization vs Tabulation

Top-Down: Memoization Bottom-Up: Tabulation

Start with the original problem, Solve smallest subproblems first,

recurse, cache results as you go. build up to original problem.

memo = {} def fib(n):

def fib(n): dp = [0] * (n+1)
if n in memo: dp[1] = 1
return memo[n] for i in range(2, n+1):
if n <= 1: dp[i] = dp[i-1]+dp[i-2]
return n return dp[n]
memo[n] = fib(n-1)+fib(n-2) # No recursion needed!
return memo[n]

✓ Intuitive ✓ Lazy evaluation ✓ No recursion ✓ Space-efficient

✗ Stack overflow risk on large n ✗ Must solve all subproblems
How to Design a DP Solution — 5 Steps

Define the Subproblem

1
Characterize the structure of an optimal solution. What smaller instances of the same problem need to be solved?

Write the Recurrence

2
Express the solution in terms of solutions to smaller subproblems. Define the base cases.

Identify Overlapping Subproblems

3
Verify the same subproblems recur multiple times (justifies storing results).

Build the DP Table

4
Choose memoization (top-down) or tabulation (bottom-up). Fill in the table in correct order.

Extract the Answer

5
Read the final answer from the table. Optionally backtrack to reconstruct the solution.
Classic Example: Fibonacci with DP

Fibonacci: f(n) = f(n-1) + f(n-2), f(0)=0, f(1)=1

DP Table (Tabulation):

n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7

0 1 1 2 3 5 8 13

Complexity Comparison:

Approach Time Complexity Space Complexity Recalculation

Naive Recursion O(2ⁿ) O(n) stack Yes — repeated

Memoization (Top-Down) O(n) O(n) No — cached

Tabulation (Bottom-Up) O(n) O(n) No — iterative

Optimized Tabulation O(n) O(1) No — 2 vars only

 SECTION 02

The Knapsack Problem

Classic DP optimization problem

The Knapsack Problem — Introduction

Problem Statement

Given n items each with a weight wᵢ and value vᵢ, and a knapsack of capacity W,
find the maximum total value that can be packed without exceeding the capacity.

0/1 Knapsack Fractional Knapsack Unbounded Knapsack

Each item can be taken Items can be broken Each item can be taken
or left (0 or 1 times). into fractions. unlimited number of times.

Solved with DP. Solved with Greedy. Solved with DP.

Time: O(nW) Time: O(n log n) Time: O(nW)
0/1 Knapsack — Recurrence Relation

Recurrence Formula:

dp[i][w] = max(dp[i-1][w], vᵢ + dp[i-1][w - wᵢ]) if wᵢ ≤ w

dp[i][w] = dp[i-1][w] if wᵢ > w
Base case: dp[0][w] = 0 for all w

Example: Items = [(wt=2, val=6), (wt=3, val=10), (wt=4, val=12)], Capacity W = 5

Item \ W 0 1 2 3 4 5

0 (none) 0 0 0 0 0 0

1 (2,6) 0 0 6 6 6 6

2 (3,10) 0 0 6 10 10 16

3 (4,12) 0 0 6 10 12 16

← Max value = 16 (take items 1 & 2: 6+10)

0/1 Knapsack — Algorithm & Code

Pseudocode

function knapsack(weights[], values[], n, W): Time Complexity

create dp[0..n][0..W] = 0 O(n × W)
n = number of items
for i = 1 to n: W = knapsack capacity
for w = 0 to W:
// Don't take item i
dp[i][w] = dp[i-1][w] Space Complexity
// Take item i (if it fits) O(n × W)
if weights[i-1] <= w: Can optimize to O(W)
take = values[i-1] + dp[i-1][w - weights[i-1]] using 1D array
dp[i][w] = max(dp[i][w], take)
Approach
return dp[n][W] // Maximum value
Bottom-Up Tabulation
Fill table row by row
Left to right

Reconstruction
Backtrack through table
If dp[i][w] ≠ dp[i-1][w]
then item i was taken
Knapsack — Space Optimization to O(W)

Key Insight: Each row dp[i] only depends on the previous row dp[i-1] → Use a single 1D array!

1D Optimized Implementation:
Critical Detail
function knapsack_1D(weights[], values[], n, W):
Why iterate W → weights[i]
dp[0..W] = 0 // 1D array
(RIGHT to LEFT)?
for i = 0 to n-1:
// MUST iterate W down to w[i]
// (prevents using item i twice)
for w = W down to weights[i]: If we go left→right, we might
dp[w] = max(dp[w], use item i more than once!
values[i] + dp[w - weights[i]])
Right→left ensures each item
return dp[W] is only used 0 or 1 times.

For Unbounded Knapsack

(items can repeat) — iterate
left→right instead.

Result: O(W) space vs O(nW) — significant saving for large n!

Knapsack — Detailed Worked Example

Items: A(w=1,v=1), B(w=2,v=6), C(w=3,v=10), D(w=5,v=16) | Capacity W=7

W=0 W=1 W=2 W=3 W=4 W=5 W=6

i=0 0 0 0 0 0 0 0

A(1,1) 0 1 1 1 1 1 1

B(2,6) 0 1 6 7 7 7 7

C(3,10) 0 1 6 10 11 16 17

D(5,16) 0 1 6 10 11 16 17

Maximum Value = 22 (Items: D+B+A = 16+6+1=23? ... B+C+A = 6+10+1=17? ... D+B=22 ✓)

Backtracking: dp[5][7]=22 ≠ dp[4][7]=17 → took D. Check dp[4][2]=6=dp[3][2]=6 → skip C. dp[3][2]=6≠dp[2][2]=1 → took B.

 SECTION 03

Longest Common Subsequence

LCS — string comparison with DP

Longest Common Subsequence (LCS) — Introduction

Definition: A subsequence of a string is derived by deleting some (or no) characters without changing order.
LCS finds the longest subsequence common to two strings.

Subsequence vs Substring: Real-World Applications:

String "ABCBDAB" Bioinformatics DNA/protein sequence alignment

"ACB", "ABB", "ABCB",

Subsequence examples Diff Tools Unix diff, Git file comparison
"ABDAB"

NOT a subsequence "BAC" (wrong order) Spell Check Edit distance computation

"BCB", "CBA" ← contiguous

Substring examples Data Dedup Finding common patterns
only

= "BCAB" or "BDAB" —
LCS("ABCBDAB", "BDCAB") Plagiarism Document similarity detection
length 4
LCS — Recurrence Relation

Recurrence Formula:

0 if i = 0 or j = 0
dp[i][j] = dp[i-1][j-1] + 1 if X[i] = Y[j] (characters match)
max(dp[i-1][j], dp[i][j-1]) if X[i] ≠ Y[j] (no match)

Intuition:

Characters match (X[i]=Y[j])

Both characters are in the LCS → extend previous LCS by 1

Characters don't match

Skip one character from either string → take the better option

Base case (i=0 or j=0)

Empty string has no common subsequence with any string → 0
LCS — Building the DP Table

Example: X = "ABCB" | Y = "BDCAB" → LCS = "BCB", length = 3

Algorithm:
B D C A B

for i = 1 to m:
0 0 0 0 0 0 for j = 1 to n:
if X[i]==Y[j]:
dp[i][j]=dp[i-1][j-1]+1
A 0 0 0 0 1 1 else:
dp[i][j]=max(dp[i-1][j],
dp[i][j-1])
B 0 1 1 1 1 2
LCS length = dp[m][n]

C 0 1 1 2 2 2

B 0 1 1 2 2 3
Backtrack to find LCS string:
Green cells = diagonal moves (character matches)
If X[i]=Y[j]: include char, go diagonal
LCS = "BCB" (length 3) — highlighted in gold Else if dp[i-1][j]>dp[i][j-1]: go up
Else: go left
LCS — Full Algorithm & Complexity

def lcs(X, Y): Time Complexity

m, n = len(X), len(Y)
# Initialize DP table O(m × n)
dp = [[0]*(n+1) for _ in range(m+1)] m = len(X), n = len(Y)
Double nested loop
# Fill DP table
for i in range(1, m+1):
for j in range(1, n+1): Space Complexity
if X[i-1] == Y[j-1]: O(m × n)
dp[i][j] = dp[i-1][j-1] + 1
for DP table
else:
Optimize to O(min(m,n))
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

return dp[m][n] # Length of LCS

LCS vs Edit Distance
def reconstruct_lcs(X, Y, dp, i, j): Edit Distance = m+n-2×LCS
if i == 0 or j == 0: Related but different
return "" problems
if X[i-1] == Y[j-1]:
return reconstruct_lcs(X, Y, dp, i-1, j-1) + X[i-1]
if dp[i-1][j] > dp[i][j-1]: LCS vs Longest
return reconstruct_lcs(X, Y, dp, i-1, j) Common Substring
return reconstruct_lcs(X, Y, dp, i, j-1) LCS: chars need not be
contiguous (subsequence)
Substring: must be continuous
LCS — Applications & Variants

Diff Algorithm (Unix/Git) DNA Sequence Alignment

$ diff [Link] AGCTTCGA

The diff tool computes LCS of lines [Link] ||| ||
< line removed Bioinformatics aligns DNA/protein AGCAAGA
between files. Lines in LCS are
> line added sequences to find evolutionary Match Score: 5/8
unchanged; others are marked as
relationships. LCS finds conserved
added/removed. Git uses this for
regions across species.
change tracking.

Shortest Common Supersequence Longest Increasing Subsequence

X=ABCB, Y=BDCAB A =
LCS=BCB (len 3) [3,1,4,1,5,9,2,6
SCS length = m + n - LCS(X, Y). The SCS SCS len = 4+5-3 LIS can be reduced to LCS problem: ]
is the shortest string that has both X = 6 LIS(A) = LCS(A, sorted(A)). Finding the LIS = [1,4,5,9]
and Y as subsequences. longest strictly increasing subsequence. len=4
via LCS with
sorted A
 SECTION 04

Matrix Chain Multiplication

Optimal parenthesization using DP

Matrix Chain Multiplication — Introduction

Problem: Given a chain of n matrices A₁, A₂, ..., Aₙ, find the most efficient way to multiply them (minimize scalar
multiplications).

Why does parenthesization matter?

Matrix multiplication is associative: (AB)C = A(BC)

but the number of operations can differ dramatically!

Example: A(10×30) × B(30×5) × C(5×60)

✓ OPTIMAL (A×B)×C: 10×30×5 + 10×5×60 = 1500+3000 = 4500 ops

✗ 6× WORSE A×(B×C): 30×5×60 + 10×30×60 = 9000+18000 = 27000 ops

MCM — Naive Approach vs Dynamic Programming

How many ways to parenthesize n matrices?

n (matrices) 2 3 4 5 6 10

Ways P(n) 1 2 5 14 42 4862 2,

P(n) = Catalan number = Ω(4ⁿ/n^1.5) — grows exponentially!

DP Complexity:

Method Time Space Practical?

Naive (enumerate all) O(2ⁿ) — No (n>15 infeasible)

Recursive with memo O(n³) O(n²) Yes

DP Tabulation (best) O(n³) O(n²) Yes — standard choice

DP reduces exponential naive to polynomial O(n³) — dramatic improvement!

MCM — Recurrence Relation & Setup

Notation & Setup:

Matrix Aᵢ has dimensions p[i-1] × p[i].

We want: m[i][j] = minimum cost to multiply Aᵢ × Aᵢ₊₁ × ... × Aⱼ

Recurrence Formula:

m[i][j] = 0 if i = j (single matrix, no multiply)

m[i][j] = min over k=i to j-1 of:
m[i][k] + m[k+1][j] + p[i-1]×p[k]×p[j]

Meaning:

Split the chain at position k. Left part (Aᵢ to Aₖ) costs m[i][k]. Right part (Aₖ₊₁ to Aⱼ) costs m[k+1][j]. Multiplying the two resulting
matrices costs p[i-1]×p[k]×p[j]. Try all k and take the minimum.
MCM — Worked Example

Matrices: A₁(30×35), A₂(35×15), A₃(15×5), A₄(5×10), A₅(10×20), A₆(20×25)

p = [30, 35, 15, 5, 10, 20, 25]

DP Table m[i][j] (minimum cost to multiply Aᵢ...Aⱼ):

m[i][j] j=1 j=2 j=3 j=4 j=5 j=6

i=1 0 15750 7875 9375 11875 15125

i=2 - 0 2625 4375 7125 10500

i=3 - - 0 750 2500 5375

i=4 - - - 0 1000 3500

i=5 - - - - 0 5000

i=6 - - - - - 0

Optimal cost = m[1][6] = 15,125 scalar multiplications (highlighted in gold)

MCM — Algorithm Implementation

def matrix_chain_order(p): Time: O(n³)

n = len(p) - 1 # number of matrices
m = [[0]*n for _ in range(n)]
Three nested loops
s = [[0]*n for _ in range(n)] # split points
Over all (i,j,k) triples
# l = chain length
for l in range(2, n+1):
for i in range(n-l+1): Space: O(n²)
j = i + l - 1
m[i][j] = float('inf') Two n×n tables:
# Try each split point k m[ ] for costs
for k in range(i, j): s[ ] for split points
cost = (m[i][k] + m[k+1][j]
+ p[i]*p[k+1]*p[j+1])
if cost < m[i][j]:
Fill Order
m[i][j] = cost
s[i][j] = k # remember split By increasing chain length l
return m[0][n-1], s l=1: diagonal (base)
l=2,3,...,n: upper triangle
def print_optimal(s, i, j):
if i == j:
print(f'A{i+1}', end='')
else:
Reconstruct
k = s[i][j] s[i][j] stores optimal k
print('(', end='')
Recurse using s table
print_optimal(s, i, k)
print_optimal(s, k+1, j) to print parenthesization
print(')', end='')
Comparison of DP Problems

Problem DP Type Subproblem Recurrence Time Space

Fibonacci 1D Linear f(n) f(n)=f(n-1)+f(n-2) O(n) O(n)/O(1)

0/1 Knapsack 2D Grid dp[i][w] max(skip, take) O(nW) O(nW)/O(W)

LCS 2D Grid dp[i][j] match or skip O(mn) O(mn)

MCM Interval DP m[i][j] min over split k O(n³) O(n²)

Coin Change 1D Linear dp[w] min coins for w O(nW) O(W)

Edit Distance 2D Grid dp[i][j] insert/del/replace O(mn) O(mn)

DP Problem Solving Strategy — Flowchart

How to recognize and solve a DP problem:

Read the problem

Does it ask for optimal Try Greedy

No
(max/min) or count? or Divide & Conquer
Yes ↓

Check: Optimal substructure?

+ Overlapping subproblems?

Define dp[i] or dp[i][j]

Write recurrence

Code it! (memoize or tabulate)

Module 4 Summary — Key Takeaways

01 Principles of DP 02 0/1 Knapsack

• Optimal substructure + overlapping subproblems → use DP • dp[i][w] = max value with i items and capacity w
• Memoization (top-down) vs Tabulation (bottom-up) • Two choices per item: take or skip
• Design steps: subproblem → recurrence → table → answer • Time O(nW), can optimize space to O(W)

03 LCS 04 Matrix Chain Multiplication

• dp[i][j] = LCS length of X[1..i] and Y[1..j] • m[i][j] = min cost to multiply Aᵢ...Aⱼ
• If X[i]=Y[j]: dp[i][j] = dp[i-1][j-1] + 1 • Try all split points k; take minimum
• Time O(mn), reconstruct by backtracking • Interval DP, O(n³) time, O(n²) space
 MODULE 4 · DYNAMIC PROGRAMMING

Thank You!
Practice Problems:

1. Coin Change (min coins) • 2. Longest Increasing Subsequence

3. Edit Distance • 4. Rod Cutting Problem • 5. Palindrome Partitioning

6. Egg Drop Problem • 7. Optimal BST • 8. Travelling Salesman (DP)

Questions & Discussions Welcome!

Computer Science Department · Algorithm Design & Analysis · 30 Hours