64. Minimum Path Sum

Posted on Edited on In

64. Minimum Path Sum

Description

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:

1
2
3
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:

1
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

Hints/Notes

  • 2024/07/31
  • dp
  • No solution from 0x3F

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!i && !j) {
                    dp[i][j] = grid[i][j];
                    continue;
                }
                int top = i ? dp[i - 1][j] : INT_MAX;
                int left = j ? dp[i][j - 1] : INT_MAX;
                dp[i][j] = min(top, left) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};