leetcode------Minimum Path Sum

标题：	Minimum Path Sum
通过率：	31.7%
难度：	中等

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.

前边做了一个类似的，跳格子，只能向右或者向下走，也就是动态规划了，在过渡一下就跟最短路径一样了。

本题的动态规划就是每一步的上一步一定是从上边或者左边来的，那么距离的累加就是F（i,j）=min(f(i-1,j),F(i,j-1))

有个小的地方就是先把第一行和第一列先累加起来，那么处理起来就是从第(1,1)位置开始计算，这样就不用去考虑边界的问题

代码如下:

public class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        for(int i=1;i<m;i++){
            grid[i][0]+=grid[i-1][0];
        }
        for(int j=1;j<n;j++){
            grid[0][j]+=grid[0][j-1];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}