Problem overview
The function min_path_sum receives a grid of non-negative integers as a Vec<Vec<i32>> with n rows and m columns. A path starts at the top-left cell and ends at the bottom-right cell, moving only down or right. The task is the smallest possible sum of the numbers along such a path.
For the grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7, from the path 1, 3, 1, 1, 1 (right, right, down, down). The statement sets O(n * m) time and O(n * m) extra space.
Approach: best path from each cell, cached
Define min_sum(i, j) as the smallest sum of a path from cell (i, j) to the bottom-right corner. From any cell you can step down or step right, so:
- at the bottom-right cell the answer is that cell's own value;
- elsewhere it is the cell's value plus the smaller of
min_sum(i + 1, j)andmin_sum(i, j + 1), using only the moves that stay inside the grid.
Written as plain recursion, this branches in two at every cell, and the same cells are reached by many different routes. The number of paths grows exponentially, but there are only n * m different cells. A table with one slot per cell, filled the first time and read afterwards, brings the work down to O(n * m).
On the example grid, the bottom-right cell is 1. The cell above it is 1 and has only the move down, so its answer is 2. The cell to the left of the corner is 2, with only the move right, so its answer is 3. The cell with 5 can go down (cost 3) or right (cost 2), so it costs 5 + 2 = 7. Continuing up and left, min_sum(0, 0) comes out as 7.
Step by step
- Read the dimensions into
nandmwithlen(). - Create the cache as a vector of vectors the same size as the grid, filled with -1. The value -1 means "not computed yet" and can't be mistaken for a real sum, because sums are never negative.
- Start the recursion from cell (0, 0):
Self::min_sum(&grid, &mut cache, 0, 0)is the final expression. - Declare
min_sumtaking the grid by shared borrow, the cache by mutable borrow and twousizeindices, returningi32. - Read the dimensions again inside it, to know where the grid ends.
- Base case: at
i == n - 1 && j == m - 1, returngrid[i][j]. - Cache hit: if
cache[i][j]is not -1, return it. - Cost of moving down: recurse into
(i + 1, j)wheni + 1 < n, and usei32::MAXotherwise. - Cost of moving right: recurse into
(i, j + 1)whenj + 1 < m, and usei32::MAXotherwise. - Combine and store:
cache[i][j] = grid[i][j] + down.min(right). - Return
cache[i][j]as the final expression.
The solution in Rust
impl Solution {
fn min_sum(grid: &Vec<Vec<i32>>, cache: &mut Vec<Vec<i32>>, i: usize, j: usize) -> i32 {
let n = grid.len();
let m = grid[0].len();
if i == n - 1 && j == m - 1 {
return grid[i][j];
}
if cache[i][j] != -1 {
return cache[i][j];
}
let down = if i + 1 < n {
Self::min_sum(grid, cache, i + 1, j)
} else {
i32::MAX
};
let right = if j + 1 < m {
Self::min_sum(grid, cache, i, j + 1)
} else {
i32::MAX
};
cache[i][j] = grid[i][j] + down.min(right);
cache[i][j]
}
fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
let n = grid.len();
let m = grid[0].len();
let mut cache = vec![vec![-1i32; m]; n];
Self::min_sum(&grid, &mut cache, 0, 0)
}
}
The Rust details worth a closer look:
ifis an expression.let down = if i + 1 < n { ... } else { i32::MAX };givesdownthe value of whichever branch runs. Both branches must have the same type, herei32.- Why
i32::MAXis safe. A move that leaves the grid is given the largest possible value so thatminnever picks it. Adding it togrid[i][j]would overflow, but that only happens if both moves are impossible, and that cell is the bottom-right corner, which returned earlier. In a release build an overflow would wrap silently, and in a debug build it would panic. - Building the cache.
vec![vec![-1i32; m]; n]creates one row ofmentries and clones itntimes. Each row is a separate vector, so changing one cell doesn't affect the others. - Borrows. The helper takes
grid: &Vec<Vec<i32>>andcache: &mut Vec<Vec<i32>>. Inside it, both are already references, so recursive calls pass them by name. The mutable borrow is handed to each call and returned when it ends, which is why both recursive calls can usecacheone after the other. - Indices are
usize. Rust indexes vectors withusize, soiandjhave that type. The comparisonsi + 1 < nstay inusize, with no casts and no negative numbers. - The corner is never cached. The base case returns before the cache is read, so the bottom-right slot stays at -1. That's harmless, since nothing reads it.
Complexity
Time: O(n * m). Each cell's value is computed once, and each computation makes two recursive calls, which return immediately when the cell is cached. The total number of calls is at most a constant times the number of cells.
Space: O(n * m). The cache has one entry per cell. The recursion is at most n + m - 1 calls deep, because every call moves one step down or right.
Edge cases and common mistakes
- A single cell.
[[5]]gives 5: the start is also the end. - One row or one column.
[[1, 2, 3]]and[[1], [2], [3]]both give 6. One of the moves is always off the grid, so the other is forced. - All zeros.
[[0, 0], [0, 0]]gives 0. This is why the cache marker is -1 and not 0: 0 is a real answer. - An empty grid. It isn't a valid input. Reading
grid[0]panics with an out-of-bounds error. - Greedy choices. Always stepping towards the smaller neighbour can fail. The best path may go through a larger cell now to avoid a much larger one later.
- Forgetting to store the result. The answers stay correct, but the recursion branches without limit and becomes far too slow on large grids.
Testing
[[1, 3, 1], [1, 5, 1], [4, 2, 1]]gives 7.[[5]]gives 5.[[1, 2, 3]]gives 6.[[1, 2], [1, 1]]gives 3.[[0, 0], [0, 0]]gives 0.
