Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Minimum Path Sum

Leetcode algorithms 第 64 题:Minimum Path Sum。

题目

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.

解答

从左上角走到右下角,使得路径上的数字的和最小。使用动态规划,dp[i][j]表示从第i行第j列开始能够取得的最小和,由于每次只能向右走和向下走,于是

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

实际上还需要考虑初始化,初始化部分即为边界的情况,由于边界上的点只有一条路径可以走,可以直接计算得到结果。

具体代码如下:

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        
        int m = grid.size(), n = grid[0].size();
        
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[m-1][n-1] = grid[m-1][n-1]; //初始化
        for (int i = m-2; i >= 0; i--) dp[i][n-1] = grid[i][n-1] + dp[i+1][n-1]; //边界上只有一种走法
        for (int i = n-2; i >= 0; i--) dp[m-1][i] = grid[m-1][i] + dp[m-1][i+1];
        
        for (int i = m-2; i >= 0; i--)
            for (int j = n-2; j >= 0; j--)
                dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1]);
        
        return dp[0][0];
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论