Dynamic Programming

Grid Dynamic Programming

State is a cell: unique paths, minimum path sum, maximal square.

Medium, about 90 minutes to practise.

1Understand

The idea

Let each cell hold the answer for reaching (or starting from) that cell. Because moves only go right and down, a cell depends only on the cell above and the one to its left, so you can fill the grid row by row and keep a single row of memory.

Intuition

Let each cell hold the answer for reaching (or leaving) that cell. When moves only go right and down, a cell depends only on the cell above and the one to its left, fill row by row.

Obstacles become base cases that block a transition (contribution 0). Sometimes you may overwrite the input grid to save space.

2-D DP is still "define the state. Write the transition"; the grid just makes dependencies geometric.

What you will be able to do

  • Fill the first row and column
  • Roll the table to one row

When to use it

  • Move only right / down
  • Count paths or minimise cost on a grid

2See it

Walkthrough

Unique paths

2×3 grid, dp[r][c] = dp[r−1][c] + dp[r][c−1].

1 / 5

1
1
1
1
?
?
012345

First row/col are 1 (only one way along the edge). Cells shown row-major.

dp[0][j] = dp[i][0] = 1

Live template

Line 1 active

1dp = [[0] * cols for _ in range(rows)]
2for r in range(rows):
3 for c in range(cols):
4 dp[r][c] = cost[r][c] + min(up, left)

Complexity: time O(rows·cols), space O(cols)

Time O(rows · cols), space O(cols) with a 1-D rolling array (or O(1) extra if mutating the grid). DFS without memo is exponential; BFS counts poorly for path counts.

Read the walkthrough as text

Unique paths with obstacles. Grid 3×3 with an obstacle at (1,1).

  1. dp[0][0] = 1 if free.
  2. First row/col: only one way until an obstacle zeros the rest of that line.
  3. dp[r][c] = (0 if obstacle else dp[r-1][c] + dp[r][c-1]).
  4. Centre blocked → paths bend around; bottom-right gets the total count.

Space optimisation keeps one row: update left-to-right so dp[c] already holds the "above"/"left" you need.

3Recognise it

Kinds of problems (6)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Unique paths

    Example. Paths from top-left to bottom-right moving right/down.

    How. dp[r][c] = dp[r-1][c] + dp[r][c-1]; first row/col are 1.

  • Paths with obstacles

    Example. Same count but some cells blocked.

    How. Zero obstacle cells; only add from open neighbours.

  • Minimum path sum

    Example. Cheapest path on weighted grid.

    How. dp adds grid value plus min(up, left); init first row/col with cumulative sums.

  • Maximal square

    Example. Largest 1-square of all ones in a binary matrix.

    How. dp = min(up, left, diag)+1 on 1-cells; track best side length.

  • Triangle minimum path

    Example. Minimum sum path from top to base of a triangle.

    How. Bottom-up or rolling row: dp[j] = val + min(dp[j], dp[j+1]).

  • DFS with memoisation on a grid (longest increasing path)

    Example. Longest strictly increasing path in a matrix.

    How. DFS from each cell with @cache on (r,c); 4-dir only to greater neighbours.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Edges not initialised

    Why it happens. Interior recurrence copied to (0,0) without thinking.

    How it fails. Min path at [0][0] adds dp[-1][0], index error or garbage from wrap.

    Fix. Init row 0 and col 0 only from valid predecessors along that edge.

  • Shared rows

    Why it happens. Multiplying a row list by rows is compact Python.

    How it fails. dp = [[0]*c]*r, mutating dp[0][0] changes every row (aliased).

    Fix. Use [[0]*cols for _ in range(rows)] or list comprehension per row.

  • Obstacles propagate

    Why it happens. Zero obstacle cell stops paths, first row should “just work”.

    How it fails. Obstacle in [0][2] but first row still 1’s, paths through blocked cell counted.

    Fix. If grid[r][c] is blocked or comes from blocked predecessor, dp[r][c]=0.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons