【Minimum Path Sum】cpp

题目：

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

tips：

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

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

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

class Solution {
public:
    int minPathSum(vector<vector<int>>& 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<grid[0].size(); ++i ) dp[0][i] = dp[0][i-1]+grid[0][i];
            for ( int i=1; i<grid.size(); ++i ) dp[i][0] = dp[i-1][0]+grid[i][0];
            for ( int i=1; i<grid.size(); ++i )
            {
                for ( int j=1; j<grid[i].size(); ++j )
                {
                    dp[i][j] = min(dp[i][j-1],dp[i-1][j])+grid[i][j];
                }
            }
            return dp[grid.size()-1][grid[0].size()-1]; 
    }
};