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:

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

Solution

Approach 1: DP (can optimize to O(N) space).

Code (Python)

Approach 1:

    def minPathSum(self, grid):
        # O(N) space
        min_paths = [grid[0][0]]
        for j in range(1, len(grid[0])):
            min_paths.append(min_paths[-1] + grid[0][j])
        for i in range(1, len(grid)):
            for j in range(len(grid[0])):
                if j == 0:
                    min_paths[j] += grid[i][j]
                else:
                    min_paths[j] = min(min_paths[j], min_paths[j-1]) + grid[i][j]
        return min_paths[-1]

Code (C++)

Approach 1:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int rowSize = grid.size();
        if (rowSize == 0)
            return 0;
        int colSize = grid[0].size();
        int minSum[rowSize][colSize];
        for (int i = rowSize - 1; i >= 0; --i)
        {
            for (int j = colSize - 1; j >= 0; --j)
            {
                minSum[i][j] = grid[i][j];
                if (i < rowSize - 1 && j < colSize - 1)
                    minSum[i][j] += std::min(minSum[i+1][j], minSum[i][j+1]);
                else if (i < rowSize - 1)
                    minSum[i][j] += minSum[i+1][j];
                else if (j < colSize - 1)
                    minSum[i][j] += minSum[i][j+1];
            }
        }
        return minSum[0][0];

    }
};