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
First row/col are 1 (only one way along the edge). Cells shown row-major.
Live template
Line 1 active
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).
dp[0][0] = 1if free.- First row/col: only one way until an obstacle zeros the rest of that line.
dp[r][c] = (0 if obstacle else dp[r-1][c] + dp[r][c-1]).- 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.