Memoize Grid Paths

Practice Exercise Intermediate Medium Memoization Matrix / Grid

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement count_grid_paths(rows, cols, blocked). Start at [0,0], move only down or right, and return the number of paths to [rows-1, cols-1]. blocked is a list of blocked [row,col] cells.

Starter code

def count_grid_paths(rows, cols, blocked):
    pass

Test cases

open-grid

{
  "args": [
    3,
    3,
    []
  ]
}

Expected: 6

center-blocked

{
  "args": [
    3,
    3,
    [
      [
        1,
        1
      ]
    ]
  ]
}

Expected: 2

blocked-destination

{
  "args": [
    2,
    2,
    [
      [
        1,
        1
      ]
    ]
  ]
}

Expected: 0

Wizard outline

Step 1: Define valid recursive states
Handle out-of-bounds, blocked, and destination cells. Precise base cases make every later recurrence safe and finite.
Step 2: Combine down and right paths
Express each small-grid state as the sum of its two legal next states. Every valid path begins with exactly one down or right move, and the two groups are disjoint.
Step 3: Cache overlapping states
Memoize each cell result to support larger grids without repeated subtrees. Many path prefixes reach the same cell, whose remaining path count is identical.

Footguns and prerequisites

Forgetting to cache zero results repeats dead-end work.
Checking the destination before blocked status counts a blocked destination.
dynamic programming

Reviewed references

Python Compound Statements — Function Definitions

Recommended approach and implementation

Define a recursive cell state and memoize the number of paths from each cell to the destination.

Why it works: The base cases exactly classify invalid and terminal states. Every remaining path starts down or right, so summing those memoized subproblems counts every valid path once.

from functools import lru_cache

def count_grid_paths(rows, cols, blocked):
    blocked_cells = {tuple(cell) for cell in blocked}
    @lru_cache(None)
    def visit(row, col):
        if row >= rows or col >= cols or (row, col) in blocked_cells:
            return 0
        if row == rows - 1 and col == cols - 1:
            return 1
        return visit(row + 1, col) + visit(row, col + 1)
    return visit(0, 0)