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.
解题思路：
典型的动态规划。开辟m*n的矩阵path，path[i][j]存放从首元素(grid[0][0])到当前元素(grid[i][j])的最短路径长度。
对于每个元素来说，路径是从上或者从左边来的。
也就是说path[i][j] = min(path[i-1][j]+path[i][j-1]) + grid[i][j]。
注意：初始化第一行第一列。
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
if(grid.empty() || grid[].empty())
return ;
int m = grid.size();
int n = grid[].size();
vector<vector<int> > path(m, vector<int>(n, ));
path[][] = grid[][];
for(int i = ; i < m; i ++)
path[i][] = path[i-][] + grid[i][];
for(int i = ; i < n; i ++)
path[][i] = path[][i-] + grid[][i];
for(int i = ; i < m; i ++)
{
for(int j = ; j < n; j ++)
{
path[i][j] = min(path[i-][j], path[i][j-]) + grid[i][j];
}
}
return path[m-][n-];
}
};