Identifying the grid DP pattern
The grid DP pattern solves problems where the input is a two dimensional grid and the answer at each cell depends on a small set of neighbouring cells. These are generally medium problems where we walk the board once, and at each cell we make a local decision from a handful of answers we have already computed.
When a problem statement, or its natural recursive solution, fits the template below, it is a grid DP problem.
Given an
n x m grid, compute dp(r, c) for each cell (r, c) from a k (a small constant) sized window of neighbouring cells by combining them with the operator pair opt (for example min) and ⊕ (for example +).How to identify the grid DP pattern
There are two signals that tell us a problem fits the grid DP pattern.
There is one grid, one answer
If the input is a single two dimensional grid or matrix, and the goal is to reduce the whole board to a single value, like an optimum, a count, or a yes or no, the problem is generally a grid DP problem.
A single grid reduces to one answer.
Liking the course? Check our discounted plans to continue learning.