最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

1
2
3
4
5
6
7
8
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

代码：

88时45空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minPathSum(int[][] grid) {
    	//每次只能向下或者向右移动一步
        for(int i=0;i<grid.length;i++)
        	for(int j=0;j<grid[0].length;j++)
	        {
        		if(i==0&&j==0)continue;
        		if(i==0&&j!=0)
        		{
        			grid[i][j]=grid[i][j-1]+grid[i][j];
        			continue;
        		}
        		if(j==0&&i!=0)
        		{
        			grid[i][j]=grid[i-1][j]+grid[i][j];
        			continue;
        		}
	        	grid[i][j]=grid[i][j]+(grid[i-1][j]<=grid[i][j-1]?grid[i-1][j]:grid[i][j-1]);
	        }
        //3/n=行，3%n=第几列
    	return grid[grid.length-1][grid[0].length-1];
    }
}