Minimum Path Sum - https://leetcode.com/problems/minimum-path-sum/description/

gistfile1.txt

class Solution {
  public int minPathSum(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
      return 0;
    }   
    
    final int rows = grid.length;
    final int cols = grid[0].length;
    int[][] visited = new int[rows][cols];
    
    // populate visited
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        visited[i][j] = Integer.MAX_VALUE;
      }
    }
    
    // Lets visit each of them and indicate if it minimize the cell.
    // Only moves down and right, which means each cell can only
    // come from left or top.
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        int cellVal = grid[i][j];
        if (i == 0 && j == 0) {
          visited[i][j] = cellVal;
        } else {       
          // top ones
          if (i == 0) {
            // only add from left
            int left = visited[i][j - 1];
            
            //System.out.println("Top val: " +  (left + cellVal));
            visited[i][j] = left + cellVal;
          }        
          // left ones
          else if (j == 0) {
            // only add from top
            int top = visited[i-1][j];
            
            //System.out.println("Left val: " +  (top + cellVal));
            visited[i][j] = top + cellVal;
          } else {        
            // middle ones
            int fromTop = cellVal + visited[i-1][j];
            int fromLeft = cellVal + visited[i][j-1];
            int minVal = Math.min(fromTop, fromLeft);
            
            // System.out.println("Other val: " + minVal);
            visited[i][j] = minVal;
          }
        }
        
      }
    }
    
    return visited[rows-1][cols-1];
    
  }
}