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.

 

Hide Tags

   

 

思路：和unique path、uique path2 类似，都是动态规划，注意，这里初始值为INT_MAX

class Solution {    public:        int minPathSum(vector
      
       
         > &grid)        {            int m = grid.size();            int n = grid[0].size();            vector
        
          row(n + 1, INT_MAX);            vector
         
          
            > f(m + 1, row);            #if 0            for(int i = 0; i < m; i ++)            {                for(int j = 0; j < n; j ++)                {                    cout << grid[i][j] << "\t";                }                cout << endl;            }            cout << endl;            #endif            f[1][1] = grid[0][0];            for(int i = 1; i <= m; i ++)            {                for(int j = 1; j <= n; j ++)                {                    if(i == 1 && j == 1)                        continue;                    f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i-1][j-1];                }            }            #if 0            for(int i = 1; i <= m; i ++)            {                for(int j = 1; j <= n; j ++)                {                    cout << f[i][j] << "\t";                }                cout << endl;            }            #endif            return f[m][n];        }};