Two-dimensional Dynamic Programming
A table over a grid
The gentlest two-dimensional state: the answer at a cell, built from the cells that can reach it.
Key idea
The state sentence, with two indexes
Everything from the last unit carries over. Write what a subproblem means as a sentence, find the recurrence, decide the base case, and choose a fill order where dependencies are already present.
The only change is that the sentence now names two things. The answer at row r and column c is the number of ways to reach that cell, or the cheapest way, or whatever the question asks.
When movement is limited to right and down, the dependencies are the same whatever the question is. Below, every cell of a small grid is asked only where it can be reached from.
Why it works
Fill order follows the dependencies
Each cell reads the one above and the one to its left, so both must already be final. Iterating rows top to bottom and columns left to right guarantees that, which the listing above makes easy to check: every source named has already been printed.
State the rule generally: work out which cells a cell depends on, then choose an order where those come first. Every table in this unit is decided by that one question, and getting it wrong reads zeros rather than raising.
Gotcha
The starting cell is a case of its own
The start has no sources, so nothing in the loop can give it a value. It has to be set explicitly, and the loop body has to be written so that it does not overwrite it afterwards.
That is also where a blocked start has to be handled. Setting the starting cell to a valid value unconditionally is a real bug on inputs where the start is impassable, and those inputs exist in the hidden tests.
Tip
One row is usually enough
Every cell reads only the row above and the cell to its left, so the whole table is unnecessary. Keeping a single row and updating it in place gives the same answer in O(cols) space.
That works because when you overwrite a cell, the value it held was the row above, which you have already used. The same read-before-overwrite reasoning as everywhere else, and it is the two-dimensional version of U14's step four.
Key idea
When the grid is empty there is a closed form
With no obstacles, reaching the bottom-right of an m by n grid takes exactly m plus n minus 2 moves, of which m minus 1 must be downward. So the count is a binomial coefficient and no table is needed at all.
That is worth mentioning and worth not leading with. The table generalizes to obstacles, costs, and blocked cells; the formula does not. Give the table and note the closed form as an aside.
Cost
Cost
One pass over every cell doing constant work, so O(rows times cols) time and the same space, dropping to O(cols) with a single rolling row.
That is the standard shape for this whole unit: the time is the size of the table and the space is one slice of it.
Grid table drills
Three tables over the same grid shape, all moving right or down only. cheapest_path returns the minimum total of the values along a route. max_collected returns the maximum total. most_valuable_with_blocks does the same as max_collected except that a cell holding None cannot be entered, and returns -1 when the bottom-right cannot be reached at all.
Tests
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]] print(cheapest_path(grid), max_collected(grid)) print(cheapest_path([]), max_collected([])) blocked = [[1, 3, 1], [1, None, 1], [4, 2, 1]] print(most_valuable_with_blocks(blocked), most_valuable_with_blocks([[5]])) print(most_valuable_with_blocks([[1, None], [None, 1]]))
Output
Run the tests when you are ready.
Unique Paths
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.