Idea behind Dynamic Programming (DP) on Grids

1. Defining the state: 

Each cell in the grid represents a state, characterized by its position and any relevant information (e.g., accumulated cost). Each cell is a state, uniquely identified by its coordinates (i, j). We can store additional information depending on the problem:

• For pathfinding: accumulated cost, direction of travel.
• For counting paths: number of paths reaching the cell, specific conditions met.
• For maximum/minimum value: maximum/minimum value encountered so far.

2. Defining the transition function:

This function describes how to move from one state to another, specifying the valid moves and their associated costs. This function specifies how to move between states.

• For pathfinding: define valid moves (e.g., up, down, left, right) and their associated cost (e.g., distance, penalty).
• For counting paths: enumerate all valid transitions based on problem conditions.
• For maximum/minimum value: compare current value with neighboring values and update accordingly.

3. Defining the base cases:

Define base cases to ensure that we do not move outside the grid. These are the smallest subproblems with readily known solutions:

• For pathfinding: The Starting and Ending cells often have a cost of 0.
• For counting paths: The Starting cell/row/column is initialized to 1 as boundary of the grid might have only one path reaching them.
• For maximum/minimum value: Edges might have initial specific values.

4. Iteratively filling the DP table: 

Starting from the base cases, calculate the optimal solution for each state using the transition function and the solutions to its smaller subproblems.

• Start with the base cases and fill the table cell by cell.
• For each cell (i, j):
  • Use the transition function to consider all valid moves from neighboring cells.
  • Calculate the optimal value for the current cell based on the values of its neighbors and the transition function.
  • Update the DP table with the optimal value for cell (i, j).

Grid problems involve a 2D grid of cells, often representing a map or graph. We can apply Dynamic Programming on Grids when the solution for a cell is dependent on solutions of previously traversed cells like to find a path or count number of paths or solve an optimization problem across the grid, with certain constraints on movement or cost. In this article we are going to discuss about the idea behind Dynamic Programming on Grids with their importance, use cases and some practice problems.