Loading...
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.
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:
This chapter covers:
Click any topic to jump in
$O(mn)$ 2D DP on two strings with reconstruction via backward walk.
Insert, delete, replace as three transitions; $dp[i][j] = 1 + \min(\cdot)$.
$O(n^2)$ DP vs. the patience-sort $O(n \log n)$ tails array.
Each tackles a different aspect
Binary include/exclude with $O(nW)$ DP and 1D $O(W)$ space via reverse iteration.
Forward iteration allows item reuse — and solves minimum coin change.
Reduction to subset sum $S/2$ with 1D boolean DP and bitset speedup.
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.
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).
Define = length of LCS of prefixes and . Recurrence: if , else . Time , space reducible to . Correctness: any LCS either ends with the matching pair (use diagonal) or skips a character from one string (use one of the two neighbors).
Find the LCS of 'ABCBDAB' and 'BDCAB'.
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.
After filling the DP table, walk backward from : if , append that character and move to ; otherwise move to whichever of or has the larger value. This reconstructs one LCS in time after the DP. Storing parent pointers is optional since the DP values themselves encode the path.
Given the DP table for 'ACE' and 'ABCDE', trace back to find the LCS.