The grid problems, and their variations

A grid where you may move right and down is the friendliest shape in the subject: the dependencies are always backwards, so a row by row sweep is always valid.

The template

def grid_dp(grid, combine, initial):
    rows, cols = len(grid), len(grid[0])
    table = [[initial] * cols for _ in range(rows)]
    table[0][0] = grid[0][0]
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue
            candidates = []
            if r > 0: candidates.append(table[r-1][c])
            if c > 0: candidates.append(table[r][c-1])
            table[r][c] = grid[r][c] + combine(candidates)
    return table[rows-1][cols-1]

The operator is the problem:

Obstacles

Set the cell to the identity for the operation: zero for counting, infinity for a minimum. The recurrence then propagates the consequence with no special case downstream, and a walled off region ends up unreachable automatically.

Remember the start and end cells: a blocked start means the answer is zero however the rest of the grid looks, and a base case set before reading the obstacles will get that wrong.

Rolling to one row

Each cell reads the row above and the cell to the left, so one array is enough if filled left to right:

row = [0] * cols
row[0] = 1
for r in range(rows):
    for c in range(1, cols):
        row[c] += row[c - 1]      # row[c] is still the row above; row[c-1] is current

Left to right is required. Right to left leaves row[c-1] holding the previous row and the recurrence silently reads the wrong cell.

Where it stops being a grid DP

Allow movement in all four directions and no fill order exists, because two cells can each be on the other's best route. The problem has become a shortest path over a graph, and the tools are Dijkstra or breadth first search.

Recognising that boundary is usually the point of the follow up question, and the expected answer is naming the change rather than finding a cleverer table.

Two dimensional variants

Minimum falling path allows three predecessors instead of two. Cherry pickup runs two walkers at once, so the state becomes both positions, which is three or four dimensions after noticing both have taken the same number of steps.