coding_pk/dp/
leetcode64.rs

1pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
2    let cols = grid[0].len();
3    let rows = grid.len();
4
5    let mut res_matrix: Vec<Vec<i32>> = vec![vec![i32::MAX; cols + 1]; rows + 1];
6    res_matrix[rows][cols - 1] = 0;
7
8    for row in (0..rows).rev() {
9        for col in (0..cols).rev() {
10            res_matrix[row][col] = grid[row][col] + res_matrix[row + 1][col].min(res_matrix[row][col + 1]);
11        }
12    }
13
14    res_matrix[0][0]
15}
16
17#[cfg(test)]
18mod tests {
19    use super::*;
20
21    #[test]
22    fn test_min_path_sum() {
23        assert_eq!(
24            min_path_sum(vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]]),
25            7
26        );
27        assert_eq!(min_path_sum(vec![vec![1, 2, 3], vec![4, 5, 6]]), 12);
28    }
29}