给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-path-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路一：标准动态规划。 初试状态：f[0][0] = grid[0][0] 边界条件：i = 0或j = 0,即只有一行或一列情况下，最小和就是这一行或一列的和。 转移方程：f[i][j] = min(f[i-1][j],f[i][j-1])+grid[i][j]。
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int rows = grid.size(); int columns = grid[0].size(); if(rows == 0||columns == 0) return 0; vector<vector<int>> f(rows,vector<int>(columns,0)); //初始条件 f[0][0] = grid[0][0]; //边界条件 走第一行就是第一行的和 for (int i = 1;i < rows;++i) { f[i][0] = f[i - 1][0] + grid[i][0]; } //边界条件 走第一列就是第一列的和 for (int j = 1;j < columns;++j) { f[0][j] = f[0][j - 1] + grid[0][j]; } for(int i = 1;i< rows;++i) { for(int j = 1;j < columns;++j) { //f[i][j] = min(f[i][j-1]+f[i-1][j]) + grid[i][j]; f[i][j] =min(f[i-1][j],f[i][j-1]) + grid[i][j]; } } return f[rows - 1][columns - 1]; } };空间优化：可以借鉴不同路径 这道题优化空间的思路，我们首先初始化第一行的值。那么这就保存了在上面一行的值，然后原地修改的时候加前一项就表示从左边加，加自己的值就表示从上面加。
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int rows = grid.size(); int columns = grid[0].size(); if(rows == 0||columns == 0) return 0; vector<int> f(columns,0); f[0] = grid[0][0]; for(int j = 1;j < columns;++j) { f[j] = f[j-1] + grid[0][j]; } for(int i = 1;i < rows;++i) { f[0] = f[0] + grid[i][0];//第一行就位 for(int j = 1;j < columns;++j) { //f[j-1] + grid[i][j]表示从左边过来 //f[j] + grid[i][j]表示从从上边下来 f[j] = min(f[j-1] + grid[i][j],f[j] + grid[i][j]); } } return f[columns - 1]; } };