【LeetCode】最小路径和

【问题】给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:

[

[,,],

[,,],

[,,]

]

输出:

解释: 因为路径 →→→→ 的总和最小。

解题思路：

这道题目也是一个经典的动态规划题目，首先题目中说明了：每次只能向下走或者向右移动一步，因此我们可以建立一个dp矩阵，大小为m行n列，其中dp[i][j]表示从左上角[0][0]位置到[i][j]位置的最小路径和。因此我们可以得到递推式为：

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

注意i=0或者j=0时，即第一行或者第一列，数组会越界，因此需要进行判断。对于i=0的情况：dp[i][j]=dp[i][j-1]+grid[i][j], j=0的情况同理可得！
当我们得到递推式以后，就可以很快的写出代码了，主要是注意不要越界就好了，并且由于我们代码循环中没有判断i,j同时为零的情况，因此需要对其进行初始化！

class Solution {

public:

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

        int m = grid.size();

        int n = grid[].size();

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

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

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

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

                if(i ==  && j != )  dp[i][j] = dp[i][j-] + grid[i][j];

                if(i !=  && j == )  dp[i][j] = dp[i-][j] + grid[i][j];

                if(i !=  && j != ){

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

                }

            }

        }

        return dp[m-][n-];

    }

};

同时，我们可以将上面的代码进行优化处理，不使用额外的空间dp矩阵，而是将dp矩阵建立在原数据grid上，但我以为这样会改变原数据，工程中不可以，但优化空间还是OK的！

class Solution {

public:

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

        int m = grid.size(), n = grid[].size();

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

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

                if(i ==  && j != ) grid[i][j] += grid[i][j-];

                if(i !=  && j == ) grid[i][j] += grid[i-][j];

                if(i * j != )

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

            }

        }

        return grid[m-][n-];

    }

};

巴特西

【LeetCode】最小路径和

最新文章

热门文章