sundeepblue
5/1/2014 - 10:56 PM

[dp] [path] [matrix] minimum path sum in 2d matrix / grid with non-negative numbers. find a path from top left to bottom right which minimiz

[dp] [path] [matrix] minimum path sum in 2d matrix / grid with non-negative numbers. find a path from top left to bottom right which minimizes the sum of all numbers along its path. can only move either down or right at any point in time.

minPathSum.cpp
content_copyfile_download
// DP, space O(M*N)
int minPathSum(vector<vector<int>> &grid) {
	if(grid.empty()) return 0;
	int m = grid.size(), n = grid[0].size();
	vector<vector<int>> sum(m, vector<int>(n, 0));
	sum[0][0] = grid[0][0];
	for(int c=1; c<n; c++) sum[0][c] = sum[0][c-1] + grid[0][c];
	for(int r=1; r<m; r++) sum[r][0] = sum[r-1][0] + grid[r][0];
	for(int r=1; r<m; r++) {
		for(int c=1; c<n; c++) {
			sum[r][c] = grid[r][c] + min(sum[r-1][c], sum[r][c-1]);
		}
	}
	return sum[m-1][n-1];
}

// DP, space O(N)
int minPathSum(vector<vector<int>>& grid) {
    int M = grid.size(), N = grid[0].size();
    vector<int> row(N, 0);
    row[0] = grid[0][0];                    // gist
    for(int c=1; c<N; c++) 
        row[c] = row[c-1] + grid[0][c];
    for(int r=1; r<M; r++) {
        row[0] += grid[r][0];               // gist 
        for(int c=1; c<N; c++) {
            row[c] = min(row[c], row[c-1]) + grid[r][c];
        }
    }
    return row[N-1];
}