问题描写叙述：

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.

基本思路：

此题能够用动态规划算法解决。

到达grid[i][j]仅仅有两种方式。从grid[i-1][j]向右移动或grid[i][j-1]向下移动。

(PS：i >1 , j>1);

至于i = 1 和 j = 1 的情形仅仅有一种方法能够到达，能够提前算好初始化。

然后利用上面的两种途径找最短的作为到达grid[i][j]的最短路径。

代码：

int minPathSum(vector
     
      
        > &grid) { //C++        int rows = grid.size();        if(rows == 0)            return 0;        int cols = grid[0].size();                int upLine = 0;        for(int i = 0; i < cols; i++)            upLine += grid[0][i];            for(int i = 1; i< rows; i++)            upLine += grid[i][cols-1];                //init            vector
       
        
          > record ;        for(int i = 0; i< rows; i++)        {            vector
         
           tmp(cols,upLine);            record.push_back(tmp);        }                int tmp = 0;        for(int i = 0; i < cols; i++)        {            record[0][i] = tmp+grid[0][i];            tmp = record[0][i];        }        tmp = 0;        for(int j = 0; j < rows; j++)        {            record[j][0] =tmp + grid[j][0];            tmp = record[j][0];        }                   for(int i = 1; i < rows; i++)            for(int j = 1; j < cols; j++)                record[i][j] = grid[i][j] + ((record[i][j-1] < record[i-1][j])?record[i][j-1]:record[i-1][j]);                        return record[rows-1][cols-1];    }