64

64. Minimum Path Sum (Medium)

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

Companies:
Google, Goldman Sachs, Amazon

Related Topics:
Array, Dynamic Programming, Matrix

Similar Questions:

• Unique Paths (Medium)
• Dungeon Game (Hard)
• Cherry Pickup (Hard)
• Maximum Number of Points with Cost (Medium)

Solution 1. DP

// OJ: https://leetcode.com/problems/minimum-path-sum/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(1)
class Solution {
public:
    int minPathSum(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                int sum = min(i - 1 >= 0 ? A[i - 1][j] : INT_MAX, j - 1 >= 0 ? A[i][j - 1] : INT_MAX);
                A[i][j] += sum == INT_MAX ? 0 : sum;
            }
        }
        return A[M - 1][N - 1];
    }
};