DSA DP on Grids

Grid dynamic programming fills a table where each cell holds the best answer for the grid ending at that cell. Every cell builds its answer from the cell above it and the cell to its left.

One cell, two neighbours

A path count adds the count from above and the count from the left. The two stored counts give the new count at once.

above = 3
left = 4
cell = above + left
print(cell)

The cheaper neighbour wins

A path cost adds the cell value to the cheaper stored cost. The smaller neighbour decides the stored cost.

cell_value = 5
above_cost = 7
left_cost = 2
cell_cost = cell_value + min(above_cost, left_cost)
print(cell_cost)

Edges have one route each

Cells on the first row are reached only from the left. Cells on the first column are reached only from above.

row = [1, 1, 1, 1]
col = [1, 1, 1]
print(row)
print(col)

Example

def unique_paths(rows, cols):
    table = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 or c == 0:
                table[r][c] = 1
            else:
                table[r][c] = table[r - 1][c] + table[r][c - 1]
    return table


def min_path_sum(cost):
    rows, cols = len(cost), len(cost[0])
    table = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                table[r][c] = cost[r][c]
            elif r == 0:
                table[r][c] = table[r][c - 1] + cost[r][c]
            elif c == 0:
                table[r][c] = table[r - 1][c] + cost[r][c]
            else:
                table[r][c] = min(table[r - 1][c], table[r][c - 1]) + cost[r][c]
    return table


def show(name, cost):
    paths = unique_paths(len(cost), len(cost[0]))
    sums = min_path_sum(cost)
    print(name)
    print("paths table:")
    for row in paths:
        print(row)
    print("paths to corner:", paths[-1][-1])
    print("cost table:")
    for row in sums:
        print(row)
    print("cheapest cost:", sums[-1][-1])


grid_a = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
grid_b = [[2, 1, 3, 1], [4, 2, 1, 2], [1, 5, 2, 1]]
show("Grid A", grid_a)
show("Grid B", grid_b)

Key points

A cell answer reuses the answers stored above it and to its left
Unique Paths counts routes that move only right or down
Minimum Path Sum keeps the cheapest cost of reaching each cell
The first row and first column each have only one incoming route
Filling row by row guarantees both neighbours are ready before use

In this example, one template solves both problems on two grids. The paths table adds the top and left counts at every cell. The cost table adds the cell value to the cheaper of those neighbours. Grid A gives 6 paths and a cheapest cost of 7. Grid B gives 10 paths and a cheapest cost of 9.

Note

A grid with r rows and c columns needs r times c table cells

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def unique_paths(rows, cols):
    table = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 or c == 0:
                table[r][c] = 1
            else:
                table[r][c] = table[r - 1][c] + table[r][c - 1]
    return table


def min_path_sum(cost):
    rows, cols = len(cost), len(cost[0])
    table = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                table[r][c] = cost[r][c]
            elif r == 0:
                table[r][c] = table[r][c - 1] + cost[r][c]
            elif c == 0:
                table[r][c] = table[r - 1][c] + cost[r][c]
            else:
                table[r][c] = min(table[r - 1][c], table[r][c - 1]) + cost[r][c]
    return table


def show(name, cost):
    paths = unique_paths(len(cost), len(cost[0]))
    sums = min_path_sum(cost)
    print(name)
    print("paths table:")
    for row in paths:
        print(row)
    print("paths to corner:", paths[-1][-1])
    print("cost table:")
    for row in sums:
        print(row)
    print("cheapest cost:", sums[-1][-1])


grid_a = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
grid_b = [[2, 1, 3, 1], [4, 2, 1, 2], [1, 5, 2, 1]]
show("Grid A", grid_a)
show("Grid B", grid_b)

Exercise

A paths table holds 4 above a cell and 6 to its left. What count does the cell store?

24 10 6 2