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.
思路：
这题不要想得太复杂，什么搜索策略什么贪心什么BFS
DFS。其实就是个DP基础题，迭代从上到下从左往右计算每个格子的距离就行了，目标是计算右下角的格子，没必要开二维数组，每次只需要更新一个滚动行即可。可以跟Unique Paths
II对比着看看。
状态方程：Min[i][j] = min(Min[i-1][j], Min[i][j-1]) +A[i][j];
1 int minPathSum(vector<vector<int> > &grid) { 2 int row = grid.size(); 3 if(row == 0) return 0; 4 int col = grid[0].size(); 5 if(col == 0) return 0; 6 7 vector<int> steps(col, INT_MAX);//初始值是INT_MAX, 因为第一次更新steps[j]会调用min函数 8 steps[0] = 0; 9 for(int i = 0; i < row; i++){ 10 steps[0] = steps[0] + grid[i][0]; 11 for(int j = 1; j < col; j++) { 12 steps[j] = min(steps[j], steps[j-1]) + grid[i][j]; 13 } 14 } 15 return steps[col-1]; 16 }
【题解】【矩阵】【DP】【Leetcode】Minimum Path Sum
原文：http://www.cnblogs.com/wei-li/p/MinimumPathSum.html