Dynamic Programming Problems

Why This Matters

Dynamic programming (DP) is one of the most heavily tested algorithm design paradigms in intro algorithms courses. You're being tested on your ability to recognize when a problem exhibits optimal substructure and overlapping subproblems, the two hallmarks that signal DP is the right approach.

Understanding these classic DP problems isn't about memorizing solutions. It's about recognizing problem patterns. When you see a new problem, you should ask: "Does this look like a knapsack variant? A sequence alignment problem? An optimization over intervals?" Each problem below represents a template that generalizes to dozens of related challenges. Don't just memorize the recurrence relations. Know why each problem structure demands dynamic programming and how to spot similar problems on sight.

---

Sequence-Based Problems

These problems operate on one or two sequences (strings, arrays) and build solutions by examining prefixes or suffixes. The core insight: the optimal solution for a sequence depends on optimal solutions for shorter subsequences.

Fibonacci Sequence

The Fibonacci sequence is the canonical DP example because it makes overlapping subproblems obvious.

• Recurrence: $F(n) = F(n-1) + F(n-2)$ with base cases $F(0) = 0$, $F(1) = 1$
• Why DP matters here: Naive recursion recomputes the same values over and over, ballooning to $O(2^n)$ time. Storing results (either via memoization or a bottom-up table) cuts this to $O(n)$ time and $O(n)$ space. You can even reduce space to $O(1)$ since you only need the two most recent values.
• Foundational pattern: Whenever you see a recursive solution doing redundant work, that's your signal to apply DP.

Longest Increasing Subsequence

Given an array, find the longest subsequence where each element is strictly greater than the previous. The elements do not need to be contiguous.

• DP approach: Build an array where $dp[i]$ stores the length of the longest increasing subsequence that ends at index $i$. For each $i$, check all earlier indices $j < i$: if $a[j] < a[i]$, then $dp[i] = \max(dp[i], dp[j] + 1)$. This gives an $O(n^2)$ solution.
• Faster approach: There's an $O(n \log n)$ version using binary search with a "tails" array, but the $O(n^2)$ DP is what you'll typically need to know for this course.
• Applications: Trend detection in time series data, patience sorting, and as a subroutine in more complex sequence problems.

Longest Common Subsequence

Given two sequences, find the longest subsequence present in both. Unlike substrings, the characters need not be adjacent.

• DP table: $dp[i][j]$ stores the LCS length for the first $i$ characters of sequence A and the first $j$ characters of sequence B. If the characters match ($A[i] = B[j]$), take $dp[i-1][j-1] + 1$. Otherwise, take $\max(dp[i-1][j], dp[i][j-1])$. Time and space are both $O(mn)$ where $m$ and $n$ are the sequence lengths.
• Real-world uses: Diff utilities in version control, DNA sequence comparison, plagiarism detection.

---

String Transformation Problems

These problems measure the "distance" or "cost" to transform one string into another. The DP table typically has dimensions matching the two string lengths, with each cell representing the cost for corresponding prefixes.

Edit Distance

Edit distance (also called Levenshtein distance) is the minimum number of single-character insertions, deletions, or substitutions needed to transform string A into string B.

• Recurrence: $dp[i][j] = \min(dp[i-1][j] + 1, \; dp[i][j-1] + 1, \; dp[i-1][j-1] + \text{cost})$ where cost is 0 if $A[i] = B[j]$, and 1 otherwise. The three terms correspond to a deletion, an insertion, and a substitution (or match), respectively.
• Base cases: $dp[i][0] = i$ (delete all of A) and $dp[0][j] = j$ (insert all of B).
• Applications: Spell checkers, DNA mutation analysis, fuzzy string matching in search engines.

---

Optimization with Constraints

These problems require maximizing or minimizing an objective while respecting resource constraints. The key pattern: build optimal solutions by considering whether to include each item.

Knapsack Problem

You have $n$ items, each with a weight $w_i$ and value $v_i$, and a knapsack with capacity $W$. Pick items to maximize total value without exceeding the weight limit. In the 0/1 variant, each item is either taken or left; you can't split items.

• Recurrence: $dp[i][w] = \max(dp[i-1][w], \; dp[i-1][w - w_i] + v_i)$ if $w_i \leq w$, otherwise $dp[i][w] = dp[i-1][w]$. The first option skips item $i$; the second takes it.
• Complexity: $O(nW)$, which is pseudo-polynomial. It looks polynomial, but $W$ is a numeric value, not the input size. If $W$ is exponentially large relative to the number of bits used to represent it, this blows up.
• Fractional variant: When items can be divided, a greedy approach (sort by value-to-weight ratio, take greedily) works in $O(n \log n)$. No DP needed.

Coin Change Problem

Given a set of coin denominations and a target amount $A$, find the fewest coins needed to make exactly $A$. This is essentially an unbounded knapsack since you can use each denomination multiple times.

• Recurrence: $dp[a] = \min(dp[a - c_i] + 1)$ for all coin values $c_i \leq a$, with base case $dp[0] = 0$. Initialize all other entries to infinity (meaning "not yet reachable").
• Time complexity: $O(A \cdot k)$ where $k$ is the number of denominations.
• Practical relevance: Currency systems, making change algorithms, resource allocation with discrete units.

Subset Sum Problem

Given a set of integers and a target $T$, determine whether any subset sums exactly to $T$. This is a decision problem: it returns true or false, not an optimal value.

• DP table: $dp[i][s]$ is true if sum $s$ is achievable using the first $i$ elements. The recurrence is $dp[i][s] = dp[i-1][s] \;\text{OR}\; dp[i-1][s - a_i]$ (either skip or include element $i$). Runs in $O(nT)$ time.
• NP-completeness: Subset Sum is weakly NP-complete. The $O(nT)$ solution is pseudo-polynomial, just like 0/1 Knapsack.

---

Interval and Structure Optimization

These problems optimize over ways to partition or combine elements. The insight: optimal solutions for larger intervals depend on optimal solutions for smaller sub-intervals.

Matrix Chain Multiplication

Given matrices $A_1, A_2, \ldots, A_n$ to multiply, find the parenthesization that minimizes the total number of scalar multiplications. The matrix dimensions determine the cost of each pairwise multiplication.

• Interval DP pattern: $dp[i][j]$ = minimum cost to multiply matrices $i$ through $j$. You try every possible split point $k$ where $i \leq k < j$, computing $dp[i][j] = \min_{k}(dp[i][k] + dp[k+1][j] + p_{i-1} \cdot p_k \cdot p_j)$ where $p$ is the dimension array.
• Why it's $O(n^3)$: There are $O(n^2)$ subproblems (all pairs $i, j$), and each considers up to $O(n)$ split points.
• Brute force comparison: The number of possible parenthesizations is the Catalan number, which grows exponentially. DP collapses this to $O(n^3)$.

Rod Cutting Problem

Given a rod of length $n$ and a price table where length $i$ sells for $p_i$, find the cuts that maximize total revenue.

• Recurrence: $dp[j] = \max_{1 \leq i \leq j}(p_i + dp[j - i])$. You try every possible first cut of length $i$, then solve the remaining subproblem $dp[j - i]$.
• Complexity: $O(n^2)$ since for each length $j$ you consider up to $j$ cut options.
• Classic intro example: Rod Cutting is frequently the first DP problem taught because the recurrence is intuitive and easy to visualize.

---

Graph-Based Dynamic Programming

These problems apply DP to graph structures, where optimal paths are built from optimal sub-paths.

Shortest Path Problems (Floyd-Warshall)

Floyd-Warshall computes the shortest path between every pair of vertices in a weighted graph.

• DP formulation: $dp[i][j][k]$ = shortest path from vertex $i$ to vertex $j$ using only vertices $\{1, \ldots, k\}$ as intermediates. The recurrence is $dp[i][j][k] = \min(dp[i][j][k-1], \; dp[i][k][k-1] + dp[k][j][k-1])$. In practice, you overwrite in place and drop the $k$ dimension, using a single 2D table.
• Complexity: $O(V^3)$ time, $O(V^2)$ space (with the in-place optimization).
• Handles negative weights: Unlike Dijkstra's algorithm, Floyd-Warshall works with negative edge weights. It only fails if the graph contains a negative-weight cycle (which makes shortest paths undefined).

---

Quick Reference Table

---

Self-Check Questions

1. Both the Knapsack Problem and Coin Change Problem involve selecting items to reach a target. What is the key structural difference that changes how you formulate the DP recurrence?

2. You're given two strings and asked to find how "similar" they are. Which two problems from this guide could apply, and when would you choose one over the other?

3. Matrix Chain Multiplication and Rod Cutting both optimize over partitions. Why does Matrix Chain require $O(n^3)$ time while Rod Cutting only needs $O(n^2)$?

4. How do the DP tables for Longest Common Subsequence and Edit Distance differ in what each cell represents, even though both operate on two strings?

5. A problem asks whether you can partition an array into two subsets with equal sums. Which classic DP problem is this a direct application of, and what would be your target value?