DP on Grids: Unique Paths, Minimum Path Sum and Obstacles

You solve grid problems by mapping the allowed moves directly to the recurrence relation. If you can only move down or right, your current cell dp[i][j] must depend on dp[i-1][j] and dp[i][j-1]. Stop trying to memorize the code for every variation and start writing the transition based on the constraints given in the problem statement.

The logic of moves

Every grid problem is a variation of a pathfinding task. In Unique Paths, you move from (0,0) to (m-1, n-1) using only right and down moves. Because you can arrive at (i, j) from the top or the left, the number of ways to reach that cell is the sum of the ways to reach those two neighbors. The state is dp[i][j], representing the total paths to that coordinate.

When you add obstacles, the logic remains identical, but you add a condition. If grid[i][j] == 1, then dp[i][j] = 0 because no path can pass through a blocked cell. This simple check inside your nested loops handles the entire constraint. You do not need a different algorithm for obstacles; you just need a filter on your state transition.

Worked example

Consider a 2x2 grid where you want the minimum path sum. Input: [[1, 3], [1, 2]]

1. Start at dp[0][0] = 1.
2. Move right to dp[0][1]: 1 + 3 = 4.
3. Move down to dp[1][0]: 1 + 1 = 2.
4. Move to dp[1][1]: min(dp[0][1], dp[1][0]) + grid[1][1].
5. Calculation: min(4, 2) + 2 = 4.

The minimum path sum is 4. You arrive at this by looking at the previous possible states and picking the one that satisfies your objective, whether that is counting paths or minimizing a sum.

From triangle to cherry pickup

A Triangle problem is just a grid where each row has a different number of columns. You move from (i, j) to (i+1, j) or (i+1, j+1). The transition is dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i+1][j+1]). The logic is the same as the grid, just with a restricted boundary.

Cherry Pickup is the only one that feels different because you move two people at once. You track their positions as (r1, c1) and (r2, c2). Since they move simultaneously, you can simplify the state to dp[step][r1][r2]. The number of columns c1 and c2 is derived from step - r1 and step - r2. It is still just a grid problem, but you are navigating a four-dimensional space instead of a two-dimensional one.

The rule of thumb

When you see a grid problem, follow these steps to build your solution:

1. Define dp[i][j] as the answer for the sub-problem ending at (i, j).
2. Identify the allowed moves to determine which previous cells contribute to the current one.
3. Write the base case for the starting cell, usually dp[0][0].
4. Apply the transition formula inside a nested loop, adding an if condition for obstacles or boundaries.

If you are stuck, draw the grid on paper and write the values for the first two rows and columns. The pattern for the transition will appear immediately. You can practice these transitions on DSA Tracker to build the muscle memory required for these patterns.

Next step: Pick a Unique Paths II problem and write the solution using a 1D array instead of a 2D matrix to save space.

Keep going with the step-by-step visualizer and practice problems.

Further reading: Binary search trees on Wikipedia.