Identifying the interval DP pattern
The interval DP pattern solves problems where the input is a single sequence and the answer is about a contiguous range built from the strictly shorter sub-ranges created by cutting the range at an inner point. These are generally medium or hard problems where the state is defined by two indices instead of one and the subproblems lay out as a 2D table of ranges.
When a problem statement, or its natural recursive solution, fits the template below, it is an interval DP problem.
Given a sequence of length
n, compute dp(i, j) for each contiguous range [i..j] from the two sub-ranges [i..k] and [k+1..j] a cut at an inner point k creates by combining them with the operator pair (opt and ⊕).How to identify the interval DP pattern
There are two signals that tell us a problem fits the interval DP pattern.
There is an answer for every range
If the input is a single array or string, and the goal is to reduce the whole sequence to a single value, like an optimum, a count, or a yes or no, where the natural subproblem is a contiguous piece of the sequence rather than a prefix of it, the problem is generally an interval DP problem. Every contiguous range [i..j] becomes a subproblem, and the whole sequence is just the widest range [0..n-1].
Every range [i..j] of the sequence is a subproblem
Liking the course? Check our discounted plans to continue learning.