My c++ program of o(mn) time


  • 3
    B
    int minPathSum(vector<vector<int> > &grid) {
    	int m = grid.size();
    	int n = grid[0].size();
    	for (int i = 0; i<m; i++)
    	{
    		for (int j = 0; j<n; j++)
    		{
    			if (i == 0 && j == 0) continue;
    			else if (i == 0) grid[i][j] += grid[i][j - 1];
    			else if (j == 0) grid[i][j] += grid[i - 1][j];
    			else
    			{
    				if (grid[i][j - 1]<grid[i - 1][j]) grid[i][j] += grid[i][j - 1];
    				else grid[i][j] += grid[i - 1][j];
    			}
    		}
    	}
    	return grid[m - 1][n - 1];
    }

  • 1
    S

    Good solution. I think the last part can be more concise as:

     grid[i][j] += min(grid[i-1][j] + grid[i][j-1]);
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.