Grid DPPaths on a grid

01Why it exists

Reach for it when you see:Grids, movement restricted to right or down (so paths never loop back), counting paths, minimum path sum, obstacle cells, each cell depending only on the one above and the one to the left, rolling a single row to save space.

02The core idea

When the only moves on a grid are right and down, a path can never loop back to a cell it has already visited, so the whole grid is a directed acyclic graph — and "row by row from the top, left to right within each row" happens to be one of its topological orders. Define dp[r][c] as the answer for walking from the top-left corner to (r, c). By the time you fill (r, c), its only two possible sources, (r−1, c) above and (r, c−1) to the left, are already computed.

The transition only cares where the last step came from. For counting (Unique Paths), the last step into (r, c) came either from above or from the left; the two cases do not overlap and together they cover everything, so dp[r][c] = dp[r−1][c] + dp[r][c−1] by the addition rule. An obstacle has no path that can end on it, so it is set to 0. For minimum cost (Minimum Path Sum), the portion of the cheapest path before its last step must itself be the cheapest way to reach that cell — otherwise swapping in something cheaper would improve the whole thing — so dp[r][c] = min(dp[r−1][c], dp[r][c−1]) + grid[r][c]. The first row can only be reached from the left and the first column only from above, so both need handling separately.

Each cell costs O(1), making the whole thing O(mn) time. Since each row depends only on the previous one, a single row is all you need to keep: sweeping left to right, dp[c] before its update still holds the previous row's value (the cell above), while dp[c−1] already holds this row's new value (the cell to the left). That brings space down to O(n), and if there are more columns than rows you can rotate the grid 90 degrees and roll along the shorter side. Reconstructing the path does require the full table, walking back from the end and always taking the smaller source. With no obstacles, Unique Paths has the closed form C(m+n−2, m−1) — the table is really Pascal's triangle turned 45 degrees — but one obstacle kills the formula, while the DP carries on unbothered.

Common traps: allowing up or left lets paths loop, the grid stops being a DAG, and "minimum path" turns into a shortest-path problem that needs BFS or Dijkstra (see the Grid as Graph lesson). When rolling a single row the sweep must go left to right, or dp[c−1] is still the stale value. If the start cell is itself an obstacle the answer is 0. And path counts grow fast — 20×20 already overflows 32 bits. Variants: restricting transitions to the three adjacent cells of the previous row gives seam carving and Minimum Falling Path Sum; Dungeon Game requires that health never drop to 0 along the way, which forces you to fill the table backwards from the end; and two people walking at once (Cherry Pickup) means putting both positions into the state.

03The algorithm

1. 1Confirm that the allowed moves cannot loop back (right and down only, or transitions only from the previous row), which makes filling row by row, left to right, a valid order.
2. 2Define dp[r][c] as the answer for reaching (r, c). Initialise the start dp[0][0] to 1 for counting, or to grid[0][0] for cost.
3. 3The first row looks only to the left and the first column only above. Every other cell uses above + left for counting and min(above, left) + grid[r][c] for minimum cost, with obstacles set to 0 or ∞.
4. 4The answer sits in dp[m−1][n−1]. For the path itself, walk back from the end, each time stepping toward the source with the smaller dp value, and reverse at the end.
5. 5When only the answer is needed, roll a single row: dp[c] = f(dp[c], dp[c−1]), where dp[c] before the update is the cell above and dp[c−1] is the cell to the left.

04Interactive demo

The same 4×4 grid in two modes. In "Min Path Sum" the small number in a cell's bottom-right corner is the cost of entering it, blue is the cell being filled, and yellow is the source it picked — whichever of above and left is smaller. Once the table is complete, green marks the cheapest path found by walking back from the end, for a total cost of 9. In "Unique Paths" yellow marks both the cell above and the cell to the left, because their route counts get added together; every cell along the edges is 1, and the bottom-right corner is 20, exactly C(6, 3).

05Code

Python has the path count rolling a single row (obstacles optional), the minimum path sum that keeps the whole table so it can reconstruct the path, and seam carving, where each row transitions from three cells. C++ has the one-dimensional versions of LeetCode 63 and 64, and checks against an empty 20×20 grid that the answer really is C(38, 19), which needs 64-bit integers.

def unique_paths(m, n, blocked=frozenset()):
    """Paths across an m×n grid from top-left to bottom-right moving only right or down; blocked holds the obstacles"""
    dp = [0] * n                     # one row is enough: before the update dp[c] is the cell above, dp[c-1] is already the cell to the left
    dp[0] = 1
    for r in range(m):
        for c in range(n):
            if (r, c) in blocked:
                dp[c] = 0                # an obstacle can never be reached
            elif c > 0:
                dp[c] += dp[c - 1]       # paths from above + paths from the left
    return dp[-1]


def min_path_sum(grid):
    """Returns (minimum cost, path). Rebuilding the path means keeping the whole table"""
    R, C = len(grid), len(grid[0])
    dp = [[0] * C for _ in range(R)]
    for r in range(R):
        for c in range(C):
            if r == 0 and c == 0:
                best = 0
            elif r == 0:
                best = dp[r][c - 1]      # the first row can only come from the left
            elif c == 0:
                best = dp[r - 1][c]      # the first column can only come from above
            else:
                best = min(dp[r - 1][c], dp[r][c - 1])
            dp[r][c] = best + grid[r][c]
    path, r, c = [], R - 1, C - 1
    while (r, c) != (0, 0):              # walk back from the end, always taking the cheaper source
        path.append((r, c))
        if c == 0 or (r > 0 and dp[r - 1][c] <= dp[r][c - 1]):
            r -= 1
        else:
            c -= 1
    return dp[-1][-1], [(0, 0)] + path[::-1]


def min_seam(energy):
    """Image seam: pick one pixel per row; the next row may only pick directly below or diagonally below. Minimise total energy"""
    prev = energy[0][:]
    for row in energy[1:]:
        prev = [row[c] + min(prev[max(c - 1, 0):c + 2]) for c in range(len(row))]
    return min(prev)


if __name__ == "__main__":
    print(unique_paths(4, 4), unique_paths(3, 3, {(1, 1)}), unique_paths(20, 20))   # 20 2 35345263800
    grid = [[1, 3, 1, 2], [1, 5, 1, 3], [4, 2, 1, 1], [2, 1, 3, 1]]   # the same grid as the interactive demo
    print(min_path_sum(grid))
    # (9, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (3, 3)])
    print(min_seam([[3, 1, 4, 2], [5, 9, 2, 6], [5, 3, 5, 8], [9, 7, 1, 3]]))   # 7 (1 → 2 → 3 → 1)

06Practice

• LeetCode 62Unique Paths (write the 2-D table first, then collapse it to one row)Medium
• LeetCode 63Unique Paths II (obstacles reset the cell to zero)Medium
• LeetCode 64Minimum Path SumMedium
• LeetCode 931Minimum Falling Path Sum (transitions from three cells in the previous row, exactly like seam carving)Medium
• LeetCode 221Maximal Square (dp is the side of the largest square whose bottom-right corner is this cell)Medium
• LeetCode 174Dungeon Game (fill the table backwards from the end)Hard