leetcode/
minimum_path_sum.rs

1//! # 64. 最小路径和
2//!
3//! 难度 中等
4//!
5//! 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
6//!
7//! 说明：每次只能向下或者向右移动一步。
8//!
9//!
10//! ## 示例 1：
11//!
12//!
13//! ```text
14//! 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
15//! 输出：7
16//! 解释：因为路径 1→3→1→1→1 的总和最小。
17//! ```
18//!
19//! ## 示例 2：
20//!
21//! ```text
22//! 输入：grid = [[1,2,3],[4,5,6]]
23//! 输出：12
24//! ```
25//!
26//! ## 提示：
27//!
28//! * `m == grid.length`
29//! * `n == grid[i].length`
30//! * `1 <= m, n <= 200`
31//! * `0 <= grid[i][j] <= 100`
32//!
33//! See [leetcode](https://leetcode-cn.com/problems/minimum-path-sum/)
34
35pub struct Solution;
36
37impl Solution {
38    pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
39        assert!(grid.len() >= 1 && grid.len() <= 200);
40        assert!(grid[0].len() >= 1 && grid[0].len() <= 200);
41
42        grid.iter().fold(None::<Vec<i32>>, |last_row, row| {
43            row.iter().enumerate().scan(None, |left, (i, &v)| {
44                assert!(v >= 0 && v <= 100);   // assume never overflow
45                *left = match (&left, &last_row) {
46                    (None, None) => v,                         // first cell
47                    (Some(left), None) => left + v,            // first row
48                    (None, Some(last_row)) => last_row[i] + v, // first column
49                    (Some(left), Some(last_row)) => std::cmp::min(*left, last_row[i]) + v,
50                }.into();
51                *left
52            }).collect::<Vec<_>>().into()
53        }).unwrap().pop().unwrap()
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test() {
63        let cases = vec![
64            (7, vec![vec![1,3,1],vec![1,5,1],vec![4,2,1]]),
65            (12, vec![vec![1,2,3],vec![4,5,6]]),
66            (14, vec![vec![1,3,4,8], vec![3,2,2,4], vec![5,7,1,9], vec![2,3,2,3]]),
67        ];
68
69        for (expect, input) in cases {
70            assert_eq!(expect, Solution::min_path_sum(input));
71        }
72    }
73}
leetcode/minimum_path_sum.rs

leetcode/
minimum_path_sum.rs
