DP on Strings

Concepts: pyStringDP, pyPalindromeDP, pyInterleave

String DP problems are a class of 2D DP where dp[i][j] represents 'the answer for the substring or prefix ending at index i of one string and index j of another (or the same) string.' The table is always (n+1) x (n+1) or (m+1) x (n+1). The fill pattern is always left-to-right, top-to-bottom. What changes is the transition: what does it mean when characters match, and what do you do when they do not? Palindrome Substrings (LeetCode 647) Count all palindromic substrings. dp[i][j] = True if s[i..j] is a palindrome. A substring is a palindrome if the outer characters match AND the inner substring is a palindrome: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Critical: fill the table by increasing substring length (diagonal order), not row by row, because dp[i][j] depends on dp[i+1][j-1] which is