These are the notes for DSA episode 69. A delivery rider picks up an order at a restaurant at the top left of a neighbourhood whose streets are all one-way: right or down. The customer is at the bottom right. How many different routes are there? And if every crossing has a wait in minutes, which route is the fastest? We write the obvious down-or-right recursion (correct, then Time Limit Exceeded on a 20 × 20 grid), draw the key insight on the grid, dp[r][c] = dp[r-1][c] + dp[r][c-1], and type it live. Then rocks on the road (unique paths II), the cheapest route dp[r][c] = g[r][c] + min(above, left) on a 1,000 × 1,000 city, one row (left to right this time), the route itself, and three real bugs. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| The delivery rider | In code |
|---|---|
| The neighbourhood's streets | a grid of m rows × n columns |
| The restaurant (top left) | start cell (0, 0) |
| The customer (bottom right) | end cell (m - 1, n - 1) |
| One-way streets | moves: one step right or one step down |
| Different routes | unique paths (count) |
| Minutes waiting at a crossing | g[r][c], the cost of a cell |
| The fastest route | minimum path sum |
| A street blocked by a rock | g[r][c] = 1 in unique paths II |
Every word, from zero
- Grid: a table of cells in rows and columns; cell
(r, c)is rowr, columnc, counted from 0. - Path / route: the sequence of cells the rider visits from start to end.
- Unique paths: the number of different routes using only right and down moves.
- Path sum: the total of the cell costs along a route, start and end included.
- State: the few numbers that fully describe a sub-problem; here
(r, c), the cell. - Recurrence: the formula for a state in terms of smaller states (above + left, or cost + min).
- Base case: states we know directly: the top row and the left column.
- Tabulation (bottom-up): filling the table in an order where every needed cell is already done (row by row, left to right).
- Overflow: a number too big for its type wraps around (an
intholds at most 2,147,483,647); Java gives no error. - Rolling array / one row: keeping only one row of the table instead of all of it.
- Combination
C(a, b): the number of ways to choosebthings out ofa.
Problem statement
Unique paths (LeetCode 62). A robot (our rider) starts at the top-left cell of an m × n grid and can only move right or down. Count the routes to the bottom-right cell. 1 ≤ m, n ≤ 100; the answer is at most 2 × 10^9.
| m | n | Answer |
|---|---|---|
| 3 | 7 | 28 |
| 3 | 2 | 3 (RDD, DRD, DDR) |
| 1 | 1 | 1 (already there) |
| 1 | 5 | 1 |
| 5 | 1 | 1 |
Minimum path sum (LeetCode 64). Each cell has a cost ≥ 0. Same moves. Return the smallest total cost of a route (start and end included). 1 ≤ m, n ≤ 200.
| grid | Answer |
|---|---|
[[1,3,1],[1,5,1],[4,2,1]] |
7 (1 → 3 → 1 → 1 → 1) |
[[1,2,3],[4,5,6]] |
12 (1 → 2 → 3 → 6) |
[[5]] |
5 |
[[1,2,3]] |
6 |
[[1],[2],[3]] |
6 |
Unique paths II (LeetCode 63). Like unique paths, but g[r][c] = 1 is a rock that no route may pass.
Obvious idea: go down, or go right
From a cell, the routes are the routes after going down plus the routes after going right. Off the grid: 0. At the end: 1.
import java.util.*;
public class Main {
static long uniquePaths(int m, int n) {
return ways(0, 0, m, n);
}
static long ways(int r, int c, int m, int n) {
if (r == m || c == n) return 0;
if (r == m - 1 && c == n - 1) return 1;
return ways(r + 1, c, m, n) + ways(r, c + 1, m, n);
}
public static void main(String[] args) {
System.out.println(uniquePaths(3, 7));
System.out.println(uniquePaths(3, 2));
System.out.println(uniquePaths(1, 1));
System.out.println(uniquePaths(1, 5));
System.out.println(uniquePaths(5, 1));
}
}
28
3
1
1
1
Correct. Now a 20 × 20 grid:
import java.util.*;
public class Main {
static long uniquePaths(int m, int n) {
return ways(0, 0, m, n);
}
static long ways(int r, int c, int m, int n) {
if (r == m || c == n) return 0;
if (r == m - 1 && c == n - 1) return 1;
return ways(r + 1, c, m, n) + ways(r, c + 1, m, n);
}
public static void main(String[] args) {
long t0 = System.nanoTime();
long w = uniquePaths(20, 20);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("20 x 20: " + w + " routes, " + ms + " ms");
}
}
Time Limit Exceeded
Why is it slow?
The recursion only ever returns 0 or 1 at the bottom, so it needs at least as many calls as there are routes: 35,345,263,800 for 20 × 20. In general about 2^(m+n). But a call depends only on two numbers, (r, c), and many routes reach the same cell (down-then-right and right-then-down both reach (1, 1)). There are only m × n = 400 different questions. Solving each once is the whole idea of DP.
The key insight: above + left
- State:
dp[r][c]= number of routes from(0, 0)into(r, c). - The last step into
(r, c)came from above(r - 1, c)or from the left(r, c - 1); the two groups never overlap. dp[r][c] = dp[r - 1][c] + dp[r][c - 1].- Base: the top row and the left column are all
1(only straight lines reach them). - Answer:
dp[m - 1][n - 1]. Fill row by row, left to right.
By hand: a 3 × 7 grid
| r \ c | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 1 | 3 | 6 | 10 | 15 | 21 | 28 = 7 + 21 |
Those are the numbers of Pascal's triangle, turned on their side: the answer is also the combination C(m + n - 2, m - 1) (choose which of the m + n - 2 moves are downs). The table is the idea that keeps working when the grid changes (rocks, costs).
Solution in Java: the 2D table
import java.util.*;
public class Main {
static long uniquePaths(int m, int n) {
long[][] dp = new long[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (r == 0 || c == 0) dp[r][c] = 1;
else dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
System.out.println(uniquePaths(3, 7));
System.out.println(uniquePaths(3, 2));
System.out.println(uniquePaths(1, 1));
System.out.println(uniquePaths(1, 5));
System.out.println(uniquePaths(5, 1));
}
}
28
3
1
1
1
The 20 × 20 grid that timed out, and 30 × 30:
import java.util.*;
public class Main {
static long uniquePaths(int m, int n) {
long[][] dp = new long[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (r == 0 || c == 0) dp[r][c] = 1;
else dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
long t0 = System.nanoTime();
long w = uniquePaths(20, 20);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("20 x 20: " + w + " routes, " + ms + " ms");
System.out.println("30 x 30: " + uniquePaths(30, 30) + " routes");
}
}
20 x 20: 35345263800 routes, 0 ms
30 x 30: 30067266499541040 routes
long, not int: 20 × 20 already needs 35 billion (see bug 1). A 100 × 100 grid has a 59-digit answer, too big even for long (LeetCode promises answers up to 2 × 10^9); Python's integers or Java's BigInteger handle it.
Rocks on the road: unique paths II
A rock cell gets 0. The start gets 1. Every other cell: above (if it exists) + left (if it exists). The top row is not all ones any more: a rock blocks every cell after it.
import java.util.*;
public class Main {
static long withRocks(int[][] g) {
int m = g.length, n = g[0].length;
long[][] dp = new long[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (g[r][c] == 1) dp[r][c] = 0;
else if (r == 0 && c == 0) dp[r][c] = 1;
else dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
System.out.println(withRocks(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}));
System.out.println(withRocks(new int[][]{{0, 1, 0, 0}}));
System.out.println(withRocks(new int[][]{{1, 0}, {0, 0}}));
System.out.println(withRocks(new int[][]{{0, 0}, {0, 1}}));
}
}
2
0
0
0
Around the centre rock over the top or underneath: 2. A rock in a single row cuts it: 0. A rock on the start or on the end: 0.
Minimum path sum: the same shape, with min
- State:
dp[r][c]= the cheapest cost from(0, 0)into(r, c), its own cost included. dp[r][c] = g[r][c] + min(dp[r - 1][c], dp[r][c - 1]).- Base:
dp[0][0] = g[0][0]; top row and left column are running sums. - Counting routes adds the two neighbours; the cheapest route takes the minimum.
By hand: [[1,3,1],[1,5,1],[4,2,1]]
| r \ c | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 1 | 4 | 5 |
| 1 | 2 | 7 = 5 + min(4, 2) | 6 = 1 + min(5, 7) |
| 2 | 6 | 8 = 2 + min(7, 6) | 7 = 1 + min(6, 8) |
import java.util.*;
public class Main {
static int minPathSum(int[][] g) {
int m = g.length, n = g[0].length;
int[][] dp = new int[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) dp[r][c] = g[0][0];
else if (r == 0) dp[r][c] = dp[r][c - 1] + g[r][c];
else if (c == 0) dp[r][c] = dp[r - 1][c] + g[r][c];
else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + g[r][c];
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
System.out.println(minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
System.out.println(minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}));
System.out.println(minPathSum(new int[][]{{5}}));
System.out.println(minPathSum(new int[][]{{1, 2, 3}}));
System.out.println(minPathSum(new int[][]{{1}, {2}, {3}}));
}
}
7
12
5
6
6
A whole city, 1,000 × 1,000:
import java.util.*;
public class Main {
static int minPathSum(int[][] g) {
int m = g.length, n = g[0].length;
int[][] dp = new int[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) dp[r][c] = g[0][0];
else if (r == 0) dp[r][c] = dp[r][c - 1] + g[r][c];
else if (c == 0) dp[r][c] = dp[r - 1][c] + g[r][c];
else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + g[r][c];
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
System.out.println(minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
System.out.println(minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}));
int N = 1000;
int[][] city = new int[N][N];
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
city[r][c] = (r * 31 + c * 17) % 10 + 1;
long t0 = System.nanoTime();
int best = minPathSum(city);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("1000 x 1000: " + best + " minutes, " + ms + " ms");
}
}
7
12
1000 x 1000: 6596 minutes, 115 ms
One row, left to right
Row r only reads the row above (dp[c] before it is overwritten) and the cell to its left in the same row (dp[c - 1], already updated). So keep one row and loop c left to right. (In the 0/1 knapsack the loop ran down, to keep the old values; here we want the new value on the left.) Integer.MAX_VALUE makes the first row take only the left.
import java.util.*;
public class Main {
static int minPathSum(int[][] g) {
int n = g[0].length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int[] row : g)
for (int c = 0; c < n; c++)
dp[c] = row[c] + (c == 0 ? dp[0] : Math.min(dp[c], dp[c - 1]));
return dp[n - 1];
}
public static void main(String[] args) {
System.out.println(minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
System.out.println(minPathSum(new int[][]{{1, 2, 3}, {4, 5, 6}}));
System.out.println(minPathSum(new int[][]{{5}}));
System.out.println(minPathSum(new int[][]{{1, 2, 3}}));
System.out.println(minPathSum(new int[][]{{1}, {2}, {3}}));
int N = 1000;
int[][] city = new int[N][N];
for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
city[r][c] = (r * 31 + c * 17) % 10 + 1;
long t0 = System.nanoTime();
int best = minPathSum(city);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("1000 x 1000: " + best + " minutes, " + ms + " ms");
}
}
7
12
5
6
6
1000 x 1000: 6596 minutes, 25 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// Unique paths: routes into (r, c) = from above + from the left. long long: counts grow fast.
long long uniquePaths(int m, int n) {
vector<long long> dp(n, 1); // the top row: one route into every cell
for (int r = 1; r < m; r++)
for (int c = 1; c < n; c++)
dp[c] += dp[c - 1]; // dp[c] (above) + dp[c - 1] (left, this row)
return dp[n - 1];
}
// Minimum path sum: cost + min(above, left), one row, left to right.
int minPathSum(const vector<vector<int>>& g) {
int n = g[0].size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (const auto& row : g)
for (int c = 0; c < n; c++)
dp[c] = row[c] + (c == 0 ? dp[0] : min(dp[c], dp[c - 1]));
return dp[n - 1];
}
int main() {
cout << uniquePaths(3, 7) << " " << uniquePaths(3, 2) << " " << uniquePaths(1, 1) << " " << uniquePaths(20, 20) << "\n";
cout << minPathSum({{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}) << " " << minPathSum({{1, 2, 3}, {4, 5, 6}}) << " "
<< minPathSum({{5}}) << " " << minPathSum({{1, 2, 3}}) << " " << minPathSum({{1}, {2}, {3}}) << "\n";
}
28 3 1 35345263800
7 12 5 6 6
The same solution in Python
# Unique paths: routes into (r, c) = from above + from the left. Python ints never overflow.
def unique_paths(m, n):
dp = [1] * n # the top row: one route into every cell
for _ in range(1, m):
for c in range(1, n):
dp[c] += dp[c - 1] # dp[c] (above) + dp[c - 1] (left, this row)
return dp[-1]
# Minimum path sum: cost + min(above, left), one row, left to right.
def min_path_sum(g):
n = len(g[0])
dp = [float("inf")] * n
dp[0] = 0
for row in g:
for c in range(n):
dp[c] = row[c] + (dp[0] if c == 0 else min(dp[c], dp[c - 1]))
return dp[-1]
print(unique_paths(3, 7), unique_paths(3, 2), unique_paths(1, 1), unique_paths(20, 20), unique_paths(100, 100))
print(min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]), min_path_sum([[1, 2, 3], [4, 5, 6]]),
min_path_sum([[5]]), min_path_sum([[1, 2, 3]]), min_path_sum([[1], [2], [3]]))
28 3 1 35345263800 22750883079422934966181954039568885395604168260154104734000
7 12 5 6 6
Which route? Walk back
Keep the full table, start at the end and step to the cheaper of the cell above and the cell on the left (on an edge there is only one choice), then reverse.
import java.util.*;
public class Main {
static int[][] table(int[][] g) {
int m = g.length, n = g[0].length;
int[][] dp = new int[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) dp[r][c] = g[0][0];
else if (r == 0) dp[r][c] = dp[r][c - 1] + g[r][c];
else if (c == 0) dp[r][c] = dp[r - 1][c] + g[r][c];
else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + g[r][c];
}
return dp;
}
static void route(int[][] g) {
int[][] dp = table(g);
int r = g.length - 1, c = g[0].length - 1;
List<String> path = new ArrayList<>();
path.add("(" + r + "," + c + ")");
while (r > 0 || c > 0) {
if (c == 0 || (r > 0 && dp[r - 1][c] <= dp[r][c - 1])) r--;
else c--;
path.add("(" + r + "," + c + ")");
}
Collections.reverse(path);
System.out.println(path + ", cost " + dp[g.length - 1][g[0].length - 1]);
}
public static void main(String[] args) {
route(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}});
route(new int[][]{{1, 2, 3}, {4, 5, 6}});
}
}
[(0,0), (0,1), (0,2), (1,2), (2,2)], cost 7
[(0,0), (0,1), (0,2), (1,2)], cost 12
Three real bugs
Bug 1: int for route counts.
import java.util.*;
public class Main {
static int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (r == 0 || c == 0) dp[r][c] = 1;
else dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
System.out.println(uniquePaths(17, 17));
System.out.println(uniquePaths(18, 18));
}
}
601080390
-1961361076
18 × 18 has 2,333,606,220 routes, more than Integer.MAX_VALUE (2,147,483,647): it wraps around to a negative number, silently. Fix: long[][] dp.
Bug 2: loops starting at 1, edges never filled.
import java.util.*;
public class Main {
static int minPathSum(int[][] g) {
int m = g.length, n = g[0].length;
int[][] dp = new int[m][n];
dp[0][0] = g[0][0];
for (int r = 1; r < m; r++)
for (int c = 1; c < n; c++)
dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + g[r][c];
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
System.out.println(minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
}
}
2
The top row and left column stayed 0, so the minimum took "free" roads that don't exist: 2 instead of 7. Fix: fill row 0 and column 0 as running sums.
Bug 3: no special case for the edges.
import java.util.*;
public class Main {
static int minPathSum(int[][] g) {
int m = g.length, n = g[0].length;
int[][] dp = new int[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (r == 0 && c == 0) dp[r][c] = g[0][0];
else dp[r][c] = Math.min(dp[r - 1][c], dp[r][c - 1]) + g[r][c];
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
System.out.println(minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3
at Main.minPathSum(Main.java:10)
at Main.main(Main.java:15)
On the top row r - 1 is -1: there is no row above. Fix: special-case r == 0 and c == 0.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Down or right (every route) | O(2^(m+n)) | O(m + n) stack | 20 × 20: Time Limit Exceeded |
| DP table (2D) | O(m × n) | O(m × n) | 1,000 × 1,000: ~0.1 s |
| One row (1D) | O(m × n) | O(n) | 1,000 × 1,000: ~25 ms |
| Combination formula (unique paths only) | O(min(m, n)) | O(1) | breaks with rocks or costs |
For minimum path sum, O(m × n) is optimal: any cell's cost could change the answer, so every cell must be read.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
int[][] dp for route counts |
-1961361076 for 18 × 18 |
2.3 billion > int max |
long[][] dp |
| Loops start at 1 | 2 instead of 7 |
edges left at 0 | fill row 0 and column 0 |
dp[r - 1][c] on the top row |
ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3 |
no row above | special-case the edges |
| Top row = 1 with rocks | too many routes | a rock blocks the rest of the row | above + left, rock = 0 |
One row filled with 0 instead of MAX_VALUE |
wrong minimum on the first row | min picks the fake 0 |
start with Integer.MAX_VALUE, dp[0] = 0 |
| Grid DP when moves go in 4 directions | wrong answers | cells depend on each other in cycles | BFS / Dijkstra |
Mini project: the rider's app
Combine the programs: read a grid of waiting minutes (with -1 for a blocked street), print the number of routes that avoid blocked streets, the fastest time, and the fastest route as a string of moves like RRDD. Extension: when two routes tie, print both.
Practice
1. Triangle (LeetCode 120). From the top of a triangle to the bottom, moving to an adjacent number in the next row; the smallest sum.
Solution
Fill from the bottom row up: each cell plus the smaller of its two children.
# Triangle (LeetCode 120): from the bottom row up, each cell + the smaller of its two children.
def minimum_total(tri):
dp = tri[-1][:]
for r in range(len(tri) - 2, -1, -1):
for c in range(r + 1):
dp[c] = tri[r][c] + min(dp[c], dp[c + 1])
return dp[0]
print(minimum_total([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]), minimum_total([[-10]]))
11 -10
2. Minimum Falling Path Sum (LeetCode 931). From any cell of the top row, move down to the cell below, below-left or below-right; the smallest sum.
Solution
# Minimum Falling Path Sum (LeetCode 931): from above-left, above or above-right.
def min_falling_path_sum(g):
n = len(g)
dp = g[0][:]
for r in range(1, n):
dp = [g[r][c] + min(dp[max(c - 1, 0):c + 2]) for c in range(n)]
return min(dp)
print(min_falling_path_sum([[2, 1, 3], [6, 5, 4], [7, 8, 9]]), min_falling_path_sum([[-19, 57], [-40, -5]]))
13 -59
3. Maximal Square (LeetCode 221). The area of the largest square of 1s.
Solution
The side of the biggest all-1 square ending at (r, c) is 1 + min(up, left, up-left).
# Maximal Square (LeetCode 221): side of the biggest all-1 square ending at (r, c) = 1 + min(up, left, up-left).
def maximal_square(m):
rows, cols = len(m), len(m[0])
dp = [[0] * (cols + 1) for _ in range(rows + 1)]
best = 0
for r in range(rows):
for c in range(cols):
if m[r][c] == "1":
dp[r + 1][c + 1] = 1 + min(dp[r][c + 1], dp[r + 1][c], dp[r][c])
best = max(best, dp[r + 1][c + 1])
return best * best
print(maximal_square([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]),
maximal_square([["0","1"],["1","0"]]))
4 1
4. Unique Paths II in one row (LeetCode 63).
Solution
# Unique Paths II (LeetCode 63) in one row: a rock resets the cell to 0.
def unique_paths_with_obstacles(g):
n = len(g[0])
dp = [0] * n
dp[0] = 1
for row in g:
for c in range(n):
if row[c] == 1:
dp[c] = 0
elif c > 0:
dp[c] += dp[c - 1]
return dp[-1]
print(unique_paths_with_obstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]]), unique_paths_with_obstacles([[0, 1], [0, 0]]),
unique_paths_with_obstacles([[1, 0]]))
2 1 0
Quick quiz
A 3 × 3 grid with a rock in the centre, moves right or down. How many routes? A) 2 B) 3 C) 4 D) 6
Answer
A) 2. Without the rock there are C(4, 2) = 6 routes; 4 of them pass the centre. Only the route along the top and the route along the bottom remain.
Interview questions
- State and recurrence for unique paths?
dp[r][c] = dp[r-1][c] + dp[r][c-1], top row and left column = 1. - Why can you fill it row by row? Moves only go right or down, so a cell depends only on cells above and to the left, which are already filled.
- Closed form?
C(m + n - 2, m - 1); it fails as soon as there are rocks or costs. - Why does the one-row loop go left to right here, but down in the 0/1 knapsack? Here we need the new left cell; in the knapsack we need the old values.
- Complexity? O(m × n) time, O(n) space with one row.
- What if the rider could move in all 4 directions? Cells depend on each other in cycles; use BFS (equal costs) or Dijkstra (non-negative costs).
- How do you print the route? Keep the full table and walk back from the end to the cheaper neighbour.
Glossary
| Term | Meaning |
|---|---|
| Grid | Cells in rows and columns, (r, c) from 0 |
| Path / route | The cells visited from start to end |
| Unique paths | Number of right/down routes |
| Path sum | Total cost of the cells on a route |
| State | (r, c): the cell |
| Recurrence | above + left (count), cost + min(above, left) (cheapest) |
| Base case | Top row and left column |
| Tabulation | Filling the table bottom-up in a safe order |
| Overflow | A value too big for its type wraps around silently |
| Rolling array | One row instead of the whole table |
| Combination | C(a, b): ways to choose b out of a |
| Obstacle | A blocked cell (rock): 0 routes through it |
Summary
- Grid DP: moves only right or down, so
dp[r][c]depends on the cell above and the cell on the left. - Unique paths:
dp[r][c] = above + left, edges = 1,longfor the counts. The recursion is right butO(2^(m+n)). - Rocks: a rock is 0, and the edges are no longer all 1.
- Minimum path sum:
dp[r][c] = g[r][c] + min(above, left), edges are running sums; walk back for the route. - One row, left to right:
O(m × n)time,O(n)space. Next episode: partition equal subset sum, a 0/1 knapsack of true and false.