An m × n grid. You start at the top-left and may move only right or down to the bottom-right. Two classic questions:
1. Unique paths — how many ways? (often empty cells, sometimes with rocks) 2. Min path sum — each cell has a positive cost; minimize the sum along the path.
Both are DAG DP. Every cell has a unique topological order (by r + c, or just nested loops r then c). There is no cycle, so you never need a shortest-path algorithm. BFS would count edges, not sums or combinations.
function uniquePaths(m, n) {
const dp = Array.from({ length: m }, () => Array(n).fill(0));
for (let r = 0; r < m; r++) dp[r][0] = 1;
for (let c = 0; c < n; c++) dp[0][c] = 1;
for (let r = 1; r < m; r++) {
for (let c = 1; c < n; c++) {
dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
}
}
return dp[m - 1][n - 1];
}You must take exactly (m-1) downs and (n-1) rights, in some order. If the grid is empty, that is the binomial C(m+n-2, m-1). DP still matters: obstacles kill the closed form, and min path sum is not a count.
Min path sum recurrence:
dp[r][c] = grid[r][c] + min(from above, from left), with the missing neighbor treated as absent (first row has no above; first column has no left).
function minPathSum(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = grid.map((row) => row.slice());
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (r === 0 && c === 0) continue;
const up = r > 0 ? dp[r - 1][c] : Infinity;
const left = c > 0 ? dp[r][c - 1] : Infinity;
dp[r][c] = grid[r][c] + Math.min(up, left);
}
}
return dp[m - 1][n - 1];
}Checks 0/2