Understanding the palindrome DP pattern

A large family of problems asks us about a contiguous range of a sequence, where the answer is decided by comparing the two ends of the range and moving to a slightly smaller range inside it. Finding the longest stretch of a string that reads the same forwards and backwards or the fewest characters to insert to make a string symmetric are problems of this kind. The characters sit in a fixed sequence, every range is judged by its two endpoint characters, and each comparison hands the work to a shorter range.

Problems like these are solved by the palindrome DP technique, where we lay out one subproblem per contiguous range of the sequence and answer each range by comparing its two endpoint characters. When the endpoints match the range hands off to the inner range between them, and when they differ it hands off to the two ranges that drop one end. Because every answer depends on shorter ranges, we can solve the shortest ranges first and grow outward until the whole sequence is covered.

The palindrome DP pattern is a classification of problems that can be solved using the palindrome DP technique.

Note that a sequence here can be an array or a string, anything indexed by a position 0, 1, ..., n-1. From here on we will use a string as our example, since palindromes read most naturally there, but everything applies to arrays as well.

The palindrome DP table, the upper triangle with target dp(0, n-1)

In this lesson we will learn the palindrome DP technique, why it qualifies as a dynamic programming problem, and how to solve it both top-down and bottom-up.

The palindrome DP technique

Every palindrome DP problem is an instantiation of the Bellman optimality equation, and to write that equation we first fix its main components, the action set, the cost function, and the transition function. Everything else, the recurrence, the order of execution, and the target state, follows from them.