Java

MinimumPathSum.java

// 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];
    }
}