本文共 747 字，大约阅读时间需要 2 分钟。

问题分析：DP问题，f[ i, j ]  += min{ grid[i] [ j - 1], grid[ i - 1][ j ] }, 1 <= i < 行数， 1 <= j  < 列数。

第一行和只能从左到右，第一列中能从上到下，初始化一下，运用状态转移方程求解，最右下角的值就是最终的结果，我们不需要额外的存储空间。

class Solution {public:    //label：DP    int minPathSum(vector
   
    
      > &grid) {        if(grid.size() == 0) return 0;        int rows = grid.size();        int cols = grid[0].size();        // 初始条件        for(int j = 1; j < cols; ++j)        grid[0][j] += grid[0][j - 1];        for(int i = 1; i < rows; ++i)        grid[i][0] += grid[i - 1][0];        //运用状态转移函数        for(int i = 1; i < rows; ++i)        for(int j = 1; j < cols; ++j)        {            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);        }        //返回最终的状态        return grid[rows - 1][cols - 1];    }};
    
   

转载地址：http://qelji.baihongyu.com/