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.

思路：二维DP。 len[i][j] = min(len[i-1][j], len[i][j-1]) +grid[i][j];

 

1 public class Solution { 2     public int minPathSum(int[][] grid) { 3         if (grid == null || grid.length == 0 || grid[0].length == 0) 4             return 0; 5         int m = grid.length; 6         int n = grid[0].length; 7         int[][] len = new int[m][n]; 8  9         int i;10         int sum = 0;11         for (i = 0; i < m; i++) {12             sum += grid[i][0];13             len[i][0] = sum;14         }15         sum = 0;16         for (i = 0; i < n; i++) {17             sum += grid[0][i];18             len[0][i] = sum;19         }20         int j;21         for (i = 1; i < m; i++) {22             for (j = 1; j < n; j++) {23                 if (len[i][j] == 0) {24                     len[i][j] = (len[i - 1][j] < len[i][j - 1] ? len[i - 1][j]25                             : len[i][j - 1]) + grid[i][j];26                 }27 28             }29 30         }31 32         return len[m - 1][n - 1];33     }34 35     public static void main(String[] args) {36         int[][] grid = { { 1 } };37         System.out.println(new Solution().minPathSum(grid));38     }39 }