Identifying the linear DP pattern
The linear DP pattern solves problems where the input is a single sequence and the answer at each position depends on a constant number of earlier positions. These are generally easy or medium problems where we walk the sequence once, and at each position we make a local decision from a handful of answers we have already worked out.
When a problem statement, or its natural recursive solution, fits the template below, it is a linear DP problem.
Given a sequence of length
n, compute dp(i) for each position i from a k sized window of earlier or later states by combining them with the function f (for example max or min).How to identify the linear DP pattern
There are two signals that tell us a problem fits the linear DP pattern.
One sequence, one answer
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, the problem is generally a linear DP problem.
A single sequence reduces to one answer, not a structure and not a second input.
Liking the course? Check our discounted plans to continue learning.