首页 > 其他 > 详细

【LeetCode】最小路径和

时间:2019-09-15 21:10:49      阅读:171      评论:0      收藏:0      [点我收藏+]

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

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

示例:

输入:

[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 13111 的总和最小。

解题思路:

这道题目也是一个经典的动态规划题目,首先题目中说明了:每次只能向下走或者向右移动一步,因此我们可以建立一个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[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = grid[0][0];
        for(int i = 0; i < m; i++){
            for(int j = 0;j < n; j++){
                if(i == 0 && j != 0)  dp[i][j] = dp[i][j-1] + grid[i][j];
                if(i != 0 && j == 0)  dp[i][j] = dp[i-1][j] + grid[i][j];
                if(i != 0 && j != 0){
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

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

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(i == 0 && j != 0) grid[i][j] += grid[i][j-1];
                if(i != 0 && j == 0) grid[i][j] += grid[i-1][j];
                if(i * j != 0)
                    grid[i][j] += min(grid[i][j-1], grid[i-1][j]);
            }
        }
        return grid[m-1][n-1];
    }
};

 

【LeetCode】最小路径和

原文:https://www.cnblogs.com/zhudingtop/p/11523825.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!