首页 > 代码库 > 【LeetCode】064. Minimum Path Sum

【LeetCode】064. Minimum Path Sum

2024-09-20 06:40:24   217人阅读

题目：

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.

题解：

Solution 1 ()

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

　　边界的第二种处理方法：因为Solution 1 中dp初始化为最大值，故需要考虑溢出情况，所以用long整型。这个就初始化为int整型。

Solution 2 ()

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

　　解法没变，就是边界的处理上不一样，这个是先初始化边界了。

Solution 3 ()

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int dp[grid.size()][grid[0].size()];
        
        dp[0][0] = grid[0][0];
        // init first row
        for(int i = 1; i < grid[0].size(); i ++){
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        // init first col
        for(int i = 1; i < grid.size(); i ++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        } 
        for(int i = 1; i < grid.size(); i ++){
            for(int j = 1; j < grid[0].size(); j++){
                dp[i][j] = dp[i - 1][j] < dp[i][j-1]? dp[i - 1][j] + grid[i][j] : dp[i][j-1] + grid[i][j];
            }
        }        
        return dp[grid.size() - 1][grid[0].size() -1];
    }
};

 

【LeetCode】064. Minimum Path Sum


联系
我们