题目：

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
     
      
       >& grid) {            if ( grid.empty() ) return 0;            const int m = grid.size();            const int n = grid[0].size();            vector
       
         dp(n, INT_MAX);            dp[0] = 0;            for ( int i=0; i
       
      
     

tips：

典型的“DP+滚动数组”，时间复杂度O(m*n)，空间复杂度O(n)。

=============================================

第二次，用偷懒的做法了，二维dp直接写了。

class Solution {public:    int minPathSum(vector
     
      
       >& grid) {            if ( grid.empty() ) return 0;            int dp[grid.size()][grid[0].size()];            fill_n(&dp[0][0], grid.size()*grid[0].size(), 0);            dp[0][0] = grid[0][0];            for ( int i=1; i