Minimum Path Sum

来源：Leetcode

原帖：http://oj.leetcode.com/problems/minimum-path-sum/

题目：
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.
Solution: Dynamic Programming. Space O(N).

代码：

 class Solution {  
 public:  
   int minPathSum(vector<vector<int> > &grid) {  
     if (grid.empty()) return INT_MIN;  
     int M = grid.size(), N = grid[0].size(); // col  
     vector<int> dp(N, 0);  
     dp[0] = grid[0][0];  
     for (int i = 1; i < N; ++i) {  
       dp[i] = grid[0][i] + dp[i - 1];        
     }      
     for (int i = 1; i < M; ++i) { // row  
       dp[0] += grid[i][0];  
       for (int j = 1; j < N; ++j) { // col  
         dp[j] = min(dp[j - 1], dp[j]) + grid[i][j];  
       }  
     }  
     return dp[N - 1];  
   }  
 };