My accepted solution in Java


  • 4
    A

    In order to get the minimum sum to get to grid(m-1,n-1);

    So we should get the minimum sum both grid(m-1,n-1-1) and grid(m-1-1,n-1),

    So that could convert to(I using every space in grid to hold the minimum sum get to grid(i,j))

                               min( grid(i-1,j) , grid(i,j-1) ) + grid(i,j)                 i>0 && j>0
                       /  
          grid(i,j)=   |       grid(i,j-1)+grid(i,j)                                        i=0 && j>0
                       |  
                       |       grid(i-1,j)+grid(i,j)                                        i>0 && j=0 
                       \  
                               grid(0,0)                                                    i=0 && j=0
    

    Finally, the grid(m-1,n-1) is the result

    Hope you can get my point :)

    public class Solution {
        
        public int min(int a,int b)
        {
            return a>b?b:a;
        }
        
        public int minPathSum(int[][] grid) {
            if(grid.length==0) return 0;
            int m=grid.length;
            int n=grid[0].length;
            int[][] res=new int[grid.length][];
            for(int i=0;i<res.length;i++)
            {
                res[i]=Arrays.copyOf(grid[i],grid[i].length);
            }
            for(int i=1;i<n;i++)
            {
                res[0][i]+=res[0][i-1];
            }
            for(int i=1;i<m;i++)
            {
                res[i][0]+=res[i-1][0];
            }
            for(int i=1;i<m;i++)
            {
                for(int j=1;j<n;j++)
                {
                    res[i][j]+=min(res[i][j-1],res[i-1][j]);
                }
            }
            return res[m-1][n-1];
        }
    }

Log in to reply
 

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