Leecode-Minimum Path Sum in 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.

----

It's a traditional Dynamic programming problem.

All we have to do is to choose the small sum in each time then record all the entries.

So, we may have a TWO-DIMENSION ARRAY to store the value 

and the answer will be at entry[m-1][n-1] .

However, it's a waste of the memory since we don't need to save all the values in the array.

So, we can use the REFACTOR-ARRAY to reuse the value and record every row.

The answer will be the last element in the last row computation.

public class Solution {


   public int minPathSum(int[][] grid) {
     
     if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;

          int[] temp = new int[grid[0].length]; // Refactor array
        
          for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++) {
                if (j > 0)
      
                  if (i > 0)
                    temp[j] = Math.min(temp[j], temp[j - 1]);  
     // temp[j] represents a[i-1][j] , temp[j-1] represents a[i][j-1] 
                  else
                    temp[j] = temp[j - 1];
                
                temp[j] += grid[i][j];
            }
        
     //The computation of first row and the first column are simple
    //Java initiate all the elements to zero 
    // so we just need to add to get the correct value.
        
            
        
          return temp[temp.length - 1];   //answer's here
    }


}