[leetcode] Minimum Path Sum

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0){ return 0; } int m = grid.length; int n = grid[0].length; int rolling[] = new int[n]; rolling[n-1] = grid[m-1][n-1]; for (int i = n-2; i >= 0; i--){ rolling[i] = rolling[i+1]+grid[m-1][i]; } for (int i = m-2; i >= 0; i--){ rolling[n-1] += grid[i][n-1]; for (int j = n-2; j >= 0; j--){ rolling[j] = Math.min(rolling[j], rolling[j+1])+grid[i][j]; } } return rolling[0]; } }