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.

1rows, cols = 3, 32 3for r in range(rows):4    for c in range(cols):5        sources = []6        if r > 0:7            sources.append(f"({r - 1}, {c}) above")8        if c > 0:9            sources.append(f"({r}, {c - 1}) left")10        print(f"({r}, {c}) reached from:", ", ".join(sources) or "nowhere, it is the start")

The top row and left column have one source each. Everything else has two, and the start has none.

Code lab· 28 min

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.

solution.py

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 tests to see output.

Problem· 20 min

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.

1rows, cols = 3, 32 3for r in range(rows):4 for c in range(cols):5 sources = []6 if r > 0:7 sources.append(f"({r - 1}, {c}) above")8 if c > 0:9 sources.append(f"({r}, {c - 1}) left")10 print(f"({r}, {c}) reached from:", ", ".join(sources) or "nowhere, it is the start")

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]]))