PGDDSA Study · Semester 1

PGD01C02

Module 5 · Data Structures and Algorithm Design

Dynamic Programming

Core Titles

Key headlines and terms for quick recall

Dynamic Programming (DP) — solve overlapping sub-problems by storing results
Two ingredients: optimal substructure + overlapping sub-problems
Two styles: top-down (memoisation) and bottom-up (tabulation)
Classics: Fibonacci, LCS, edit distance, 0/1 Knapsack, matrix chain, coin change
Pros: optimal, polynomial time on many NP-hard-looking problems
Cons: high memory, requires recognising overlap
Master skill of competitive programming and core ML algorithms

Basic Idea

What it is, why it matters, how it works

What is DP?

Dynamic Programming solves problems with overlapping sub-problems by storing each sub-problem's answer once and reusing it. This replaces exponential recomputation with polynomial-time table lookups.

Two required ingredients

1. Optimal substructure. The optimal answer for a problem can be expressed in terms of optimal answers to smaller sub-problems.

2. Overlapping sub-problems. Sub-problems recur many times — so caching pays off. (If not, use Divide and Conquer instead.)

Two styles

1. Top-down (Memoisation). Write the natural recursion, but cache results in a dict / table. Solve only the sub-problems you need.

from functools import lru_cache
@lru_cache(None)
def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

2. Bottom-up (Tabulation). Iteratively fill a table of sub-problems from base case upward.

def fib(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Bottom-up avoids recursion overhead; top-down is often clearer.

Classic DP problems

1. Fibonacci. Naive recursion $O(2^n)$ . DP $O(n)$ time, $O(1)$ space.

2. Longest Common Subsequence (LCS). For strings $X[1..m], Y[1..n]$ : $dp[i][j] = \begin{cases} 0 & i = 0 \text{ or } j = 0 \\ dp[i-1][j-1] + 1 & X[i] = Y[j] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}$ $O(mn)$ time and space.

3. Edit Distance (Levenshtein). Minimum insertions/deletions/substitutions to convert one string to another. $O(mn)$ . Used in spell checkers, DNA alignment.

4. 0/1 Knapsack. $dp[i][w] = \max(dp[i-1][w], \; dp[i-1][w - w_i] + v_i)$ for each item $i$ and capacity $w$ . $O(nW)$ time and space.

5. Matrix Chain Multiplication. Find optimal parenthesisation. $O(n^3)$ .

6. Coin change (arbitrary denominations). Min coins to make amount $A$ . $dp[a] = \min_{c \in \text{coins}} dp[a - c] + 1$ .

7. Floyd–Warshall shortest paths. All-pairs shortest paths $O(V^3)$ .

8. Bellman–Ford. Shortest paths with negative weights.

9. Viterbi algorithm. Most likely sequence in an HMM — DP backbone of speech recognition.

Pattern for designing a DP

Define the state — what does $dp[i]$ or $dp[i][j]$ represent?
Identify base cases.
Write the recurrence — how does the current state depend on smaller states?
Choose order — bottom-up (left-to-right) or top-down.
Reconstruct the solution if needed — backtrack pointers.

Pros and cons

Pros.

Turns exponential into polynomial.
Provably optimal when structure holds.
Reconstructs solutions cleanly.

Cons.

Memory hungry ( $O(nW)$ table).
Requires recognising sub-problem structure (skill).
Many problems need space optimisation tricks (rolling array).

DP in Machine Learning

Viterbi — HMM decoding (POS tagging).
CTC loss — speech / sequence labelling.
Dynamic Time Warping — time-series matching.
Sequence alignment — bioinformatics (Smith–Waterman).
Reinforcement learning — value-iteration / policy-iteration are DP on Bellman equations.

Mind Map

Visual structure of the concept

DYNAMIC PROGRAMMING
├── Required structure
│   ├── Optimal substructure
│   └── Overlapping sub-problems
├── Styles
│   ├── Top-down (memoisation)
│   └── Bottom-up (tabulation)
├── Classics
│   ├── Fibonacci
│   ├── LCS  O(mn)
│   ├── Edit distance  O(mn)
│   ├── 0/1 Knapsack  O(nW)
│   ├── Matrix chain  O(n³)
│   ├── Coin change
│   ├── Floyd-Warshall  O(V³)
│   ├── Bellman-Ford
│   └── Viterbi (HMM)
└── Design pattern
    ├── State
    ├── Base case
    ├── Recurrence
    └── Order of filling

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. What is memoisation in dynamic programming? A top-down DP technique that caches the result of each recursive sub-problem the first time it is computed and returns the cached value on subsequent calls — turning exponential recursion into linear-time table lookups (e.g., naive Fibonacci $O(2^n) \to O(n)$ ).

Q2. State the two ingredients required for DP to apply.

Optimal substructure — the optimal answer is composed of optimal sub-answers.
Overlapping sub-problems — the same sub-problem recurs many times.

Q3. Differentiate top-down and bottom-up DP.

Top-down (memoisation) — natural recursion with cache; solves only needed sub-problems.
Bottom-up (tabulation) — iteratively fill a table from base cases; no recursion overhead.

Part B (20 marks)

Q. Explain Dynamic Programming with its required properties. Illustrate with examples — Fibonacci, Longest Common Subsequence (LCS) and 0/1 Knapsack. Compare DP with Divide and Conquer.

DP idea.

Solve a problem by storing answers to sub-problems so they aren't recomputed. Turns exponential recursion into polynomial table lookups.

Required properties.

Optimal substructure — optimal solution is built from optimal sub-solutions.
Overlapping sub-problems — sub-problems recur (if they don't, use plain divide-and-conquer).

Two styles.

Top-down (memoisation). Recurse and cache.
Bottom-up (tabulation). Iteratively fill a table.

Example 1 — Fibonacci.

Naive recursion is $O(2^n)$ :

fib(n) = fib(n-1) + fib(n-2)

fib(5) recomputes fib(2) three times.

DP version $O(n)$ :

dp[0] = 0; dp[1] = 1
for i = 2 to n:
    dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Space can be reduced to $O(1)$ (only last two values).

Example 2 — Longest Common Subsequence (LCS).

Given strings $X$ of length $m$ , $Y$ of length $n$ , find the longest subsequence common to both.

Recurrence. $dp[i][j] = \begin{cases} 0 & i = 0 \text{ or } j = 0 \\ dp[i-1][j-1] + 1 & X[i] = Y[j] \\ \max(dp[i-1][j], \, dp[i][j-1]) & \text{else} \end{cases}$

Pseudo-code.

for i = 0..m: dp[i][0] = 0
for j = 0..n: dp[0][j] = 0
for i = 1..m:
    for j = 1..n:
        if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] + 1
        else:            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]

Complexity. $O(mn)$ time and space. Used in diff utilities, bio-informatics, plagiarism detection.

Example 3 — 0/1 Knapsack.

Items $1..n$ with weights $w_i$ and values $v_i$ ; capacity $W$ . Each item taken once or not at all.

State. $dp[i][w]$ = max value using items $1..i$ with capacity $w$ .

Recurrence. $dp[i][w] = \begin{cases} dp[i-1][w] & w < w_i \\ \max(dp[i-1][w], \, dp[i-1][w - w_i] + v_i) & \text{else} \end{cases}$

Base case. $dp[0][w] = 0$ .

Answer. $dp[n][W]$ . Backtrack to recover items taken.

Complexity. $O(nW)$ time and space. Pseudo-polynomial: depends on $W$ .

Why greedy fails here. Greedy by ratio is sub-optimal because we can't take fractions.

DP vs Divide and Conquer.

Aspect	Divide & Conquer	Dynamic Programming
Sub-problems	Independent	Overlapping
Stored results	No	Yes
Typical complexity	$O(n \log n)$	$O(n^2)$ or $O(nW)$
Examples	Merge sort, FFT	LCS, knapsack
Without optimisation	$O(2^n)$ if overlap	–

Take-away. DP is the antidote to exponential recursion. Recognising overlapping sub-problems and identifying state + recurrence is the core skill — used in algorithms, NLP (Viterbi, CTC), bioinformatics (Needleman-Wunsch), reinforcement learning (Bellman equations) and many ML decoders.

Greedy Method Backtracking