Week 11

Chapter 11: Dynamic Programming Advanced

Tackle advanced DP problems involving two sequences, item selection, and subset partitioning. Master LCS, edit distance, LIS, knapsack variants, and partition problems that form the backbone of competitive programming and technical interviews.

Chapter Overview

Building on the DP fundamentals from the previous chapter, we now tackle problems that require more sophisticated state definitions and recurrences. These problems typically involve two-dimensional DP tables, multi-choice decisions at each step, and clever reductions from one problem to another.

The key themes in advanced DP are:

Dual-sequence DP: Problems like LCS and edit distance operate on two strings or sequences simultaneously, requiring a 2D table indexed by positions in both sequences
Item selection DP: Knapsack problems involve choosing from a set of items subject to a constraint, with each item either included or excluded (0/1) or used unlimited times (unbounded)
Subsequence DP: LIS requires finding optimal subsequences within a single sequence, with an elegant O(n log n) optimization using binary search
Reduction to known problems: Many problems (like partition equal subset sum) can be reformulated as variants of simpler known problems (subset sum, which is itself a knapsack variant)

This chapter covers:

Longest Common Subsequence: 2D DP on two sequences with subsequence matching
Edit Distance: Minimum operations to transform one string into another
Longest Increasing Subsequence: Classic 1D subsequence problem with an O(n log n) optimization
0/1 Knapsack: The foundational item selection problem
Unbounded Knapsack & Coin Change: Variants with unlimited item usage
Partition Equal Subset Sum: Reducing a partition problem to subset sum DP

Chapter Roadmap

Click any topic to jump in

Longest Common Subsequence

$O(mn)$ 2D DP on two strings with reconstruction via backward walk.

2D Table ConstructionReconstructing the LCS

Edit Distance

Insert, delete, replace as three transitions; $dp[i][j] = 1 + \min(\cdot)$.

Three Operations as TransitionsVisualizing the DP Table

Builds on previous

Longest Increasing Subsequence

$O(n^2)$ DP vs. the patience-sort $O(n \log n)$ tails array.

O(n^2) DP ApproachO(n log n) with Binary Search

Multiple approaches

Each tackles a different aspect

0/1 Knapsack

Binary include/exclude with $O(nW)$ DP and 1D $O(W)$ space via reverse iteration.

Include or Exclude DecisionSpace Optimization with 1D Array

Unbounded Knapsack & Coin Change

Forward iteration allows item reuse — and solves minimum coin change.

Unbounded vs 0/1 KnapsackCoin Change: Minimum Coins

Builds on previous

Partition Equal Subset Sum

Reduction to subset sum $S/2$ with 1D boolean DP and bitset speedup.

Reduction to Subset SumOptimization and Early Termination

The Longest Common Subsequence (LCS) problem asks for the longest sequence of characters that appears in both strings in the same relative order, but not necessarily contiguously. For example, the LCS of "abcde" and "ace" is "ace" with length 3.

LCS is a foundational dual-sequence DP problem. The 2D table dp[i][j] represents the LCS length for the first i characters of string 1 and the first j characters of string 2. When characters match, we extend a previous solution; when they do not, we take the better of two options---dropping a character from either string.

In this topic

12D Table Construction

2Reconstructing the LCS

1 of 2

2D Table Construction

Define dp[i][j] as the length of the LCS of text1[:i] and text2[:j]. Base cases: dp[0][j] = 0 and dp[i][0] = 0 (an empty string has no common subsequence with anything). Transition: if text1[i-1] == text2[j-1], then dp[i][j] = dp[i-1][j-1] + 1 (extend the LCS by the matching character). Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip one character from either string and keep the better result).

Mathematical Intuition

Define $dp[i][j]$ = length of LCS of prefixes $A[0..i)$ and $B[0..j)$ . Recurrence: $dp[i][j] = dp[i-1][j-1] + 1$ if $A[i-1]=B[j-1]$ , else $\max(dp[i-1][j], dp[i][j-1])$ . Time $O(mn)$ , space $O(mn)$ reducible to $O(\min(m,n))$ . Correctness: any LCS either ends with the matching pair (use diagonal) or skips a character from one string (use one of the two neighbors).

Example:

Find the LCS of 'ABCBDAB' and 'BDCAB'.

2 of 2

Reconstructing the LCS

The DP table gives us the length, but to recover the actual subsequence, we trace back from dp[m][n]. If text1[i-1] == text2[j-1], that character is part of the LCS---include it and move diagonally to dp[i-1][j-1]. Otherwise, move in the direction of the larger value: go to dp[i-1][j] if it is larger, or dp[i][j-1] otherwise. Continue until reaching row 0 or column 0.

Mathematical Intuition

After filling the DP table, walk backward from $dp[m][n]$ : if $A[i-1]=B[j-1]$ , append that character and move to $(i-1, j-1)$ ; otherwise move to whichever of $(i-1, j)$ or $(i, j-1)$ has the larger value. This reconstructs one LCS in $O(m+n)$ time after the $O(mn)$ DP. Storing parent pointers is optional since the DP values themselves encode the path.

Example:

Given the DP table for 'ACE' and 'ABCDE', trace back to find the LCS.

Blogs

Longest Common Subsequence — NeetCode 1143. Longest Common Subsequence — LeetCode Editorial Longest Common Subsequence (Hirschberg's algorithm)Longest Common Subsequence | DP-4

Dynamic Programming Basics

Advanced Data Structures