Part VII · Dynamic Programming: Comprehensive Problem Families
44. Sequence and String Dynamic Programming
6 lessons•24 topics•Intermediate / Advanced
0 of 6 lessons published
44.01Outline
Longest increasing subsequence
- O(n²) DP
- O(n log n) tails
- Strict vs non-strict
- Reconstructing LIS
44.02Outline
LCS and related
- Longest common subsequence
- Longest common substring
- Sequence alignment
- Shortest common supersequence
44.03Outline
Edit distance
- Levenshtein distance
- Insert/delete/replace costs
- Weighted edit distance
- Reconstruct edits
44.04Outline
Palindrome DP
- Longest palindromic subsequence
- Longest palindromic substring DP
- Minimum palindrome cuts
- Count palindromic subsequences
44.05Outline
String segmentation
- Word break
- Word break counting
- Regex matching DP
- Wildcard matching
44.06Outline
Sequence optimization
- Maximum sum increasing subsequence
- Bitonic subsequence
- Russian doll envelopes
- Chain pairs