ZERO / HERO
Only ever moving right or down

Grid DP & Path Counting

The analogy

Stand in the top-left of a grid and only ever step right or down. The number of ways to reach any square is the ways to reach the square above plus the square to the left. Blocked squares are simply zero, and the same walk finds the cheapest route if the squares have costs.

Visualizer

Paths through the grid

step 1 / 9
c0c1c2c3c4
r0
r1█
r2█
r3

A 4×5 grid with two blocked cells. Count paths from top-left to bottom-right, moving only RIGHT or DOWN.moves: right and down only

def unique_paths(grid):                 # 1 = blocked
    n, m = len(grid), len(grid[0])
    dp = [0] * m
    dp[0] = 1
    for i in range(n):
        for j in range(m):
            if grid[i][j]:
                dp[j] = 0                  # obstacle
            elif j > 0:
                dp[j] += dp[j-1]           # from the left
    return dp[-1]                          # O(m) space

def min_path_sum(grid):
    n, m = len(grid), len(grid[0])
    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0: continue
            up   = grid[i-1][j] if i else float("inf")
            left = grid[i][j-1] if j else float("inf")
            grid[i][j] += min(up, left)     # in place, O(1) extra
    return grid[-1][-1]

# four-directional movement => cycles => use Dijkstra / 0-1 BFS
Check yourself

Movement becomes four-directional with positive costs. Still DP?