LeetCode Q64: 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.

	class Solution {
	public:
	int minPathSum(vector<vector<int>>& grid) {
	int m=grid.size();
	int n=grid[0].size();
	vector<vector<int>> dp(m+1,vector<int>(n+1,0));
	for(int i=1; i<=m; i++){
	for(int j=1; j<=n; j++){
	if(dp[i][j]!=0){
	if(i==1){
	dp[i][j]=min(dp[i][j], dp[i][j-1]+grid[i-1][j-1]);
	continue;
	}
	if(j==1){
	dp[i][j]=min(dp[i][j], dp[i-1][j]+grid[i-1][j-1]);
	continue;
	}
	dp[i][j]=min(dp[i][j], min(dp[i-1][j], dp[i][j-1])+grid[i-1][j-1]);;
	}
	else
	{
	if(i==1){
	dp[i][j]=dp[i][j-1]+grid[i-1][j-1];
	continue;
	}
	if(j==1){
	dp[i][j]=dp[i-1][j]+grid[i-1][j-1];
	continue;
	}
	dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i-1][j-1];
	}
	}
	}
	return dp[m][n];
	}
	};

view raw Q64MinimumPathSum.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int minPathSum(vector<vector<int>>& grid) {
	if(grid.empty())
	return 0;
	int m=grid.size(), n=grid[0].size();
	vector<vector<int> > sums(m+1, vector<int>(n+1, 0));
	for(int i=1; i<=m; i++)
	for(int j=1; j<=n; j++){
	if(i==1)
	sums[i][j]=grid[i-1][j-1]+sums[i][j-1];
	if(j==1)
	sums[i][j]=grid[i-1][j-1]+sums[i-1][j];
	if(i!=1&&j!=1)
	sums[i][j]=grid[i-1][j-1]+min(sums[i-1][j], sums[i][j-1]);
	}
	return sums[m][n];
	}
	};

view raw Q64.cpp hosted with ❤ by GitHub