LintCode-Minimum Path Sum

 1 public class Solution {
 2     /**
 3      * @param grid: a list of lists of integers.
 4      * @return: An integer, minimizes the sum of all numbers along its path
 5      */
 6     public int minPathSum(int[][] grid) {
 7         int rowNum = grid.length;
 8         if (rowNum==0) return 0;
 9         int colNum = grid[0].length;
10         if (colNum==0) return 0;
11         
12         int[][] sum = new int[rowNum][colNum];
13         sum[0][0] = grid[0][0];
14         for (int i=1;i<rowNum;i++) sum[i][0] = sum[i-1][0]+grid[i][0];
15         for (int i=1;i<colNum;i++) sum[0][i] = sum[0][i-1]+grid[0][i];
16         
17         for (int i=1;i<rowNum;i++)
18             for (int j=1;j<colNum;j++){
19                 sum[i][j] = Math.min(sum[i-1][j],sum[i][j-1])+grid[i][j];
20             }
21                 
22         return sum[rowNum-1][colNum-1];
23     }
24 }