Algorithms
Dynamic Programming (Advanced)
Difficulty: Advanced
Edit distance, the minimum number of insertions, deletions, and substitutions to turn one string into another, is what every spell checker quietly computes when it suggests a correction. The DP table that solves it has m n cells, each...
Dynamic Programming (Advanced)
Edit distance, the minimum number of insertions, deletions, and substitutions to turn one string into another, is what every spell checker quietly computes when it suggests a correction. The DP table that solves it has m * n cells, each filled by looking at three neighbors. That single 2D recurrence is the gateway to a much larger family: longest common subsequence, knapsack, palindrome partitioning, regex matching, and many more.
Dynamic Programming (Advanced) is where 1D DP graduates into the rest of the field. You will work through 2D grid and string DP (unique paths, edit distance, LCS, longest common substring), the knapsack family (0/1, unbounded, subset sum, coin change), sequence DP (LIS in O(n^2) and the patience-sorting O(n log n) variant, maximum product subarray, word break), string DP (palindromic subsequence and substring, regex and wildcard matching), DP on trees (diameter, max path sum, binary tree cameras), interval DP via matrix chain multiplication, and an introduction to bitmask DP for TSP and assignment problems.
In Dynamic Programming (Intro), you learned to define state, transition, and base cases on linear problems. This lesson layers a second dimension onto each.
Next, Advanced DP Techniques introduces optimization tools that push DP beyond standard tabulation.
Prerequisites:
Dynamic Programming (Intro)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement 2D DP solutions for grid paths, edit distance, and longest common subsequence.
Solve 0/1 knapsack, unbounded knapsack, and subset sum using tabulation with space optimization.
Implement LIS using both the O(n^2) DP approach and the O(n log n) binary search optimization.
Apply string DP to find the longest palindromic subsequence.
Understand DP on trees through the tree diameter problem and identify when tree DP is appropriate.
Explain bitmask DP and recognize problems where state can be encoded as a bitmask.
Why This Matters
01
2D DP problems like edit distance and LCS appear frequently in coding interviews at top companies and form the basis of real-world applications like spell checkers, diff tools, and DNA sequence alignment.
02
The 0/1 knapsack pattern is a template for resource allocation problems and appears in many optimization interview questions including subset sum and partition equal subset.
03
Longest Increasing Subsequence (LIS) with the O(n log n) binary search optimization is a classic example of combining DP with other techniques for better performance.
04
DP on trees and bitmask DP extend the paradigm to non-linear structures, covering advanced interview and competitive programming problems.
Key Terms
8 terms you'll encounter in this lesson
2D DP
Dynamic programming where the state is defined by two parameters, typically represented as a 2D table dp[i][j]. Common in string comparison and grid path problems.
Edit distance (Levenshtein)
The minimum number of single-character insertions, deletions, or substitutions to transform one string into another. Solved with a 2D DP table in O(m*n) time.
Longest Common Subsequence (LCS)
The longest sequence of characters that appears in both strings in the same order (not necessarily contiguous). A classic 2D DP problem.
0/1 Knapsack
An optimization problem where each item can be taken or left (0 or 1 times). Maximize total value without exceeding a weight capacity. Solved with 2D DP in O(n*W) time.
Longest Increasing Subsequence (LIS)
The longest subsequence of an array where each element is strictly greater than the previous one. Can be solved in O(n log n) using patience sorting with binary search.
Interval DP
DP where subproblems are defined over contiguous intervals [i, j]. Used in matrix chain multiplication and optimal BST problems. The interval length grows from small to large.
Bitmask DP
DP where a subset of elements is encoded as a bitmask (integer). Each bit represents whether an element is included. Enables DP over subsets in O(2^n * n) time.
DP on Trees
Dynamic programming applied to tree structures where dp[node] depends on the DP values of its children. Solved via post-order DFS traversal.
Heads Up
Common misconceptions to watch out for
"LCS and longest common substring are the same"
LCS allows non-contiguous characters (subsequence), while longest common substring requires contiguous characters. 'ACE' is a subsequence of 'ABCDE' but 'ACE' is not a substring.
"0/1 knapsack can be solved greedily by value-to-weight ratio"
Greedy by value/weight ratio works for fractional knapsack but fails for 0/1 knapsack. For example, items with values [60,100,120] and weights [10,20,30] with capacity 50: greedy picks items 1+2 (160) but optimal is items 2+3 (220).
"LIS must use O(n^2) DP"
The O(n^2) approach works but is not optimal. The patience sorting approach with binary search achieves O(n log n) by maintaining a list of smallest tail values for increasing subsequences of each length.
"2D DP always needs O(m*n) space"
When each row only depends on the previous row (like edit distance and knapsack), you can optimize to O(min(m,n)) space using a single-row rolling array.