【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 ;

            const int m = grid.size();

            const int n = grid[].size();

            vector<int> dp(n, INT_MAX);

            dp[] = ;

            for ( int i=; i<m; ++i )

            {

                dp[] += grid[i][];

                for ( int j=; j<n; ++j )

                {

                    dp[j] = grid[i][j] + std::min(dp[j-], dp[j]);

                }

            }

            return dp[n-];

    }

};

tips：

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

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

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

class Solution {

public:

    int minPathSum(vector<vector<int>>& grid) {

            if ( grid.empty() ) return ;

            int dp[grid.size()][grid[].size()];

            fill_n(&dp[][], grid.size()*grid[].size(), );

            dp[][] = grid[][];

            for ( int i=; i<grid[].size(); ++i ) dp[][i] = dp[][i-]+grid[][i];

            for ( int i=; i<grid.size(); ++i ) dp[i][] = dp[i-][]+grid[i][];

            for ( int i=; i<grid.size(); ++i )

            {

                for ( int j=; j<grid[i].size(); ++j )

                {

                    dp[i][j] = min(dp[i][j-],dp[i-][j])+grid[i][j];

                }

            }

            return dp[grid.size()-][grid[].size()-];

    }

};

巴特西

【Minimum Path Sum】cpp

最新文章

热门文章