64. Minimum Path Sum

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] <= 100

Rust Solution

struct Solution;

impl Solution {
    fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let m = grid[0].len();
        let mut dp: Vec<Vec<i32>> = vec![vec![0; m]; n];
        dp[0][0] = grid[0][0];
        for j in 1..m {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for i in 1..n {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for i in 1..n {
            for j in 1..m {
                dp[i][j] = i32::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        dp[n - 1][m - 1]
    }
}

#[test]
fn test() {
    let grid: Vec<Vec<i32>> = vec_vec_i32![[1, 3, 1], [1, 5, 1], [4, 2, 1]];
    let res = 7;
    assert_eq!(Solution::min_path_sum(grid), res);
}

Having problems with this solution? Click here to submit an issue on github.