Filling a grid where each cell comes from its top and its left
Tier 1LockedWhere it runs
1. The problem
A robot stands in the top-left corner of a warehouse grid and has to reach the bottom-right corner. It moves only right or down, one cell per move. Planning raises two questions. How many different routes are there? And which route is the cheapest, if crossing each cell costs something (the aisle is crowded, or there is a slope)?
Trying the routes by hand soon becomes impossible. An 8 by 8 grid already has 3432 of them, and a real warehouse plan has far more cells.
In the previous lesson you filled one row of cells. Here the answer depends on two coordinates, the row and the column, so the row turns into a grid of cells. The idea stays the same: you fill each cell from cells you have already filled.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- best/maximum/minimum ending at position i
- ways to reach, climb, or tile
- cannot pick two adjacent items
- minimum cost path through a grid
- overlapping subproblems, same state recomputed
Looks similar, isn't
- Recursion with memoization
Memoisation fills the same table from the top, on demand. This fills it upward in a fixed order.
- Greedy (exchange argument)
Greedy commits to one choice per step. DP keeps every option until the end.
- Recursion
The recursion tells you what the transition is. The table is what makes it fast.
- DP on subsequences (LIS / LCS / edit distance)
There the state is a pair of positions in two sequences. Here one index is enough.
n states with O(1) work each gives O(n). Memory drops to O(1) when only the last states matter.
On LeetCode
Grid problems where you move only right or down and want the number of routes or the cheapest route. Each cell comes from the cell above and the cell to the left, so one pass row by row fills the table.
The lesson's countPaths with nothing blocked.
The lesson's countPaths with obstacles, where a blocked cell holds 0.
The lesson's minPathCost, word for word.
Each spot comes from the two spots above it, so fill row by row and take the smallest number in the last row.
A cell's square side is 1 plus the smallest of its top, left and top-left neighbours, one neighbour more than in the lesson.