Lesson 31.3 · DP on Strings and Sequences
Palindromic DP and Pattern Matching
Palindromes use an interval state dp[i][j] over one string. Matching problems (interleaving, wildcards, counting subsequences) are two-sequence tables with their own rules.
12 min
Think of it like this
Checking a word for symmetry by peeling letters off both ends: the answer for the whole word depends on the answer for the middle.
1.Palindromes
Longest palindromic subsequence: dp[i][j] for s[i..j]. If s[i] == s[j], dp[i + 1][j − 1] + 2; else max(dp[i + 1][j], dp[i][j − 1]). Fill by increasing length (or i from right to left). It also equals LCS(s, reverse(s)).
Counting palindromic substrings is simpler with expand-around-centre (Module 3): O(n²) time, O(1) space.
2.Matching rules
Distinct subsequences (how many ways t appears in s): if s[i] == t[j], you may use it or not: dp[i][j] = dp[i − 1][j − 1] + dp[i − 1][j].
Interleaving: dp[i][j] = s3's first i + j characters can interleave s1[0..i) and s2[0..j); take the last character from either string if it matches.
Wildcards (? any one char, * any sequence): * either matches nothing (dp[i][j − 1]) or one more character (dp[i − 1][j]).
Remember
- Interval state for one-string symmetry.
- Write the rule for the last character, then the table follows.
Common mistakes
- Filling interval DP row by row from the top (dp[i + 1][…] isn't ready yet).