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.
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<int> help(n,0); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(j==0){ help[j] += grid[i][j]; continue; } if(i==0){ help[j] =help[j-1] + grid[i][j]; }else{ help[j] = min(help[j-1],help[j])+grid[i][j]; } } } return help[n-1]; } };
原文：http://www.cnblogs.com/zengzy/p/5003774.html