Minimum Path Sum (Java)

 

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.

 

Apply DFS first failed on time limitation, then adopted DP with 2 dimension matrix passed OJ, finally refector code to use 1 dimension rotational array

	// Failed on time limitation, faster solution below
	public class Solution {
	public int minPathSum(int[][] grid) {
	if (grid==null || grid.length==0){
	return 0;
	}
	int[] minPath={Integer.MAX_VALUE};
	int currentX=0;
	int currentY=0;
	int lastValue=0;
	calMinPath(grid, currentX, currentY, lastValue,minPath);
	return minPath[0];
	}
	private void calMinPath(int[][] grid, int currentX, int currentY, int lastValue, int[] minPath){
	if (currentX>=grid[0].length || currentY>=grid.length){
	return;
	}
	if (currentX==grid[0].length-1 && currentY==grid.length-1){
	if (minPath[0]>lastValue+grid[currentY][currentX]){
	minPath[0]=lastValue+grid[currentY][currentX];
	}
	return;
	}
	calMinPath(grid, currentX+1, currentY, lastValue+grid[currentY][currentX], minPath);
	calMinPath(grid, currentX, currentY+1, lastValue+grid[currentY][currentX], minPath);
	}
	}
	// 2 Dimention DP Solution passed OJ
	public class Solution {
	public int minPathSum(int[][] grid) {
	if (grid==null || grid.length==0){
	return 0;
	}
	int[][] minCounter=new int[grid.length][grid[0].length];
	minCounter[0][0]=grid[0][0];
	// build first column
	for (int i=1; i<grid.length; i++){
	minCounter[i][0]=grid[i][0]+minCounter[i-1][0];
	}
	// build first row
	for (int i=1; i<grid[0].length; i++){
	minCounter[0][i]=grid[0][i]+minCounter[0][i-1];
	}
	//build minCounter
	for (int i=1; i<grid.length; i++){
	for (int j=1; j<grid[0].length; j++){
	minCounter[i][j]=Math.min(minCounter[i-1][j], minCounter[i][j-1])+grid[i][j];
	}
	}
	return minCounter[grid.length-1][grid[0].length-1];
	}
	}
	// 1 dimentional rotation array
	public class Solution {
	public int minPathSum(int[][] grid) {
	if (grid==null || grid.length==0){
	return 0;
	}
	int[] steps=new int[grid[0].length];
	// initialize the steps array
	steps[0]=grid[0][0];
	for (int col=1; col<grid[0].length; col++){
	steps[col]=steps[col-1]+grid[0][col];
	}
	// start from row 1, calculate the min path
	for (int row=1; row<grid.length; row++){
	steps[0]=steps[0]+grid[row][0];
	for (int col=1; col<grid[0].length; col++){
	// steps[col] can be regard as the up neighbor of current point in 2D matrix
	// steps[col-1] can be regard as the left neighbor of current point in 2D matrix
	steps[col]=Math.min(steps[col], steps[col-1])+grid[row][col];
	}
	}
	return steps[steps.length-1];
	}
	}

view raw MinimumPathSum.java hosted with ❤ by GitHub