The problem. Given an m × n grid of non-negative numbers, find a path from the top-left to the bottom-right, moving only right or down, that minimises the sum of the numbers on it. Return that sum.
grid = [[1,3,1],[1,5,1],[4,2,1]] -> 7 (1 → 3 → 1 → 1 → 1)
grid = [[1,2,3],[4,5,6]] -> 12 (1 → 2 → 3 → 6)Let best[r][c] be the cheapest sum of a path from the start to (r, c), including both ends. The last step came from above or from the left, so best[r][c] = grid[r][c] + min(best[r−1][c], best[r][c−1]). Along the top row and the left column there's only one way in. It's Unique Paths with min and + instead of +.
function minPathSum(grid) { const memo = new Map(); const best = (r, c) => { // the cheapest path sum to (r, c) if (r < 0 || c < 0) return Infinity; // off the grid: never chosen if (r === 0 && c === 0) return grid[0][0]; const key = r * grid[0].length + c; if (!memo.has(key)) memo.set(key, grid[r][c] + Math.min(best(r - 1, c), best(r, c - 1))); return memo.get(key); }; return best(grid.length - 1, grid[0].length - 1);}Time O(m · n), space O(m · n). Off-grid cells return infinity so min never picks them — but INT_MAX + grid[r][c] would overflow, which is why the start is handled before reaching them.
Each cell adds its own cost to the cheaper of the cells above and to the left.
function minPathSum(grid) { const m = grid.length, n = grid[0].length; const best = Array.from({ length: m }, () => new Array(n).fill(0)); for (let r = 0; r < m; r++) { for (let c = 0; c < n; c++) { if (r === 0 && c === 0) best[r][c] = grid[r][c]; else if (r === 0) best[r][c] = grid[r][c] + best[r][c - 1]; // top row: only from the left else if (c === 0) best[r][c] = grid[r][c] + best[r - 1][c]; // left column: only from above else best[r][c] = grid[r][c] + Math.min(best[r - 1][c], best[r][c - 1]); } } return best[m - 1][n - 1];}Time O(m · n), space O(m · n).
function minPathSum(grid) { const n = grid[0].length; const row = new Array(n).fill(Infinity); row[0] = 0; for (const cells of grid) { row[0] += cells[0]; // left column: only from above for (let c = 1; c < n; c++) row[c] = cells[c] + Math.min(row[c], row[c - 1]); // above or left } return row[n - 1];}Time O(m · n), space O(n). Starting the row at infinity (except row[0]) makes the first row only take values from the left.
