64. Minimum Path Sum Medium

1/**
2 * [64] Minimum Path Sum
3 *
4 * Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
5 * Note: You can only move either down or right at any point in time.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg" style="width: 242px; height: 242px;" />
9 * Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
10 * Output: 7
11 * Explanation: Because the path 1 &rarr; 3 &rarr; 1 &rarr; 1 &rarr; 1 minimizes the sum.
12 *
13 * Example 2:
14 *
15 * Input: grid = [[1,2,3],[4,5,6]]
16 * Output: 12
17 *
18 *  
19 * Constraints:
20 *
21 * m == grid.length
22 * n == grid[i].length
23 * 1 <= m, n <= 200
24 * 0 <= grid[i][j] <= 100
25 *
26 */
27pub struct Solution {}
28
29// problem: https://leetcode.com/problems/minimum-path-sum/
30// discuss: https://leetcode.com/problems/minimum-path-sum/discuss/?currentPage=1&orderBy=most_votes&query=
31
32// submission codes start here
33use std::cmp;
34
35impl Solution {
36    pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
37        let mut min = vec![vec![0; grid[0].len()]; grid.len()];
38
39        for i in 0..grid.len() {
40            for j in 0..grid[i].len() {
41                if i == 0 && j == 0 {
42                    min[i][j] = grid[i][j];
43                } else if i == 0 {
44                    min[i][j] = grid[i][j] + min[i][j - 1];
45                } else if j == 0 {
46                    min[i][j] = grid[i][j] + min[i - 1][j];
47                } else {
48                    min[i][j] = grid[i][j] + cmp::min(min[i - 1][j], min[i][j - 1])
49                }
50            }
51        }
52
53        min[grid.len() - 1][grid[0].len() - 1]
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_64() {
65        assert_eq!(
66            Solution::min_path_sum(vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]]),
67            7
68        );
69    }
70}
71