a direct way to solve in java


  • 0
    A

    it is about 4 ms solution,

    public class Solution {
        public int minPathSum(int[][] grid) {
            int[][] pa = grid;
            if(grid.length<2&&grid[0].length<2)return grid[0][0];
            if(grid.length<2){
                 for(int i = 1; i < pa[0].length; i++) {
                        pa[0][i] = pa[0][i]+pa[0][i-1];
                    }
                 return pa[0][pa[0].length-1];
                
            }
            if(grid[0].length<2){
                 for(int i = 1; i < pa.length; i++) {
                        pa[i][0] = pa[i][0]+pa[i-1][0];
                    }
                 return pa[pa.length-1][0];
                
            }
            for(int i = 1; i < pa[0].length; i++) {
                pa[0][i] = pa[0][i]+pa[0][i-1];
            }
            for(int i = 1; i < pa.length; i++) {
                pa[i][0] = pa[i-1][0]+pa[i][0];
                for(int j = 1; j < pa[i].length;j++) {
                    pa[i][j] = Math.min(pa[i][j]+pa[i][j-1],pa[i][j]+pa[i-1][j]);
                }
            }
            return pa[pa.length-1][pa[0].length-1];
        }
    }
    

Log in to reply
 

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