leetcode64. Minimum Path Sum

这个题是从左上角到右下角的路径和最小，实际就是一道dp题。

第一种写法是只初始化（0，0）位置，第二种写法则是把第一行、第一列都初始化了。个人更喜欢第二种写法，简单一点。

dp的右下角的值就为最终的值

第一种写法：

class Solution {

public:

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

        int rows = grid.size();

        if(rows <= )

            return -;

        int cols = grid[].size();

        if(cols <= )

            return -;

        vector<vector<int> > result(rows,vector<int>(cols));

        result[][] = grid[][];

        for(int i = ;i < rows;i++){

            for(int j = ;j < cols;j++){

                if(i !=  && j != )

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

                if(i ==  && j != )

                    result[i][j] = result[i][j-] + grid[i][j];

                if(j ==  && i != )

                    result[i][j] = result[i-][j] + grid[i][j];

            }

        }

        return result[rows-][cols-];

    }

};

第二种写法：

class Solution {

public:

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

        int m = grid.size();

        if(m <= )

            return ;

        int n = grid[].size();

        if(n <= )

            return ;

        vector<vector<int> > dp(m,vector<int>(n));

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

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

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

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

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

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

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

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

            }

        }

        return dp[m-][n-];

    }

};

巴特西

leetcode64. Minimum Path Sum

最新文章

热门文章