64. Minimum Path Sum

Description of Problem

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.

Note: You can only move either down or right at any point in time.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

Solution

Code (Rust)

impl Solution {
    pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = if m > 0 {grid[0].len()} else {0};
        let mut sum = vec![ vec![0; n]; m];

        for i in 0..m{
            for j in 0..n{
                match (i > 0,j > 0) {
                    (false, false) => {
                        sum[i][j] = grid[i][j];
                    },
                    (false, true) => {
                        sum[i][j] = grid[i][j] + sum[i][j-1];
                    },
                    (true, false) => {
                        sum[i][j] = grid[i][j] + sum[i-1][j];
                    },
                    (true, true) => {
                        sum[i][j] = grid[i][j] + sum[i-1][j].min(sum[i][j-1]);
                    },
                }
            }
        }


        return sum[m-1][n-1];
    }
}

Complexity

Time Complexity

• \(T(m,n)=\Theta(m \ n)\)

Auxiliary Space

• \(S(m,n)=O(m \ n)\)