Leetcode: Minimum Path Sum

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.

与Unique Path问题相似，是一个DP问题，解决问题的方案依然是建造一个新矩阵，每个元素值是从top left到该点的最短距离。递归式可以根据这个写出来，并且一旦计算出了到该点的最短距离，就把它存起来以备其他点使用。

递推式是res[i][j]=min(res[i-1][j], res[i][j-1])+grid[i][j]。总共进行两层循环，时间复杂度是O(m*n)。空间复杂度本来应该是O(M*N)的一个矩阵，但是我们实际需要的其实只有上一行的信息，这样可以省去一维，只需要O(m)就够了

注意12行是从左到右

 1 public int minPathSum(int[][] grid) {
 2     if(grid == null || grid.length==0 || grid[0].length==0)
 3         return 0;
 4     int[] res = new int[grid[0].length];
 5     res[0] = grid[0][0];
 6     for(int i=1;i<grid[0].length;i++)
 7     {
 8         res[i] = res[i-1]+grid[0][i];
 9     }
10     for(int i=1;i<grid.length;i++)
11     {
12         for(int j=0;j<grid[0].length;j++)
13         {
14             if(j==0)
15                 res[j] += grid[i][j];
16             else
17                 res[j] = Math.min(res[j-1], res[j])+grid[i][j];
18         }
19     }
20     return res[grid[0].length-1];
21 }