首页 > 代码库 > LeetCode:Minimum Path Sum

LeetCode:Minimum Path Sum

2024-07-07 10:05:04   231人阅读

题目链接

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]表示从左上角到grid[i][j]的最小路径和。那么dp[i][j] = grid[i][j] + min( dp[i-1][j], dp[i][j-1] );

下面的代码中，为了处理计算第一行和第一列的边界条件，我们令dp[i][j]表示从左上角到grid[i-1][j-1]的最小路径和，最后dp[m][n]是我们所求的结果

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int row = grid.size(),col;
        if(row == 0)return 0;
        else col = grid[0].size();
        vector<vector<int> >dp(row+1, vector<int>(col+1, INT_MAX));
        dp[0][1] = 0;
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= col; j++)
                dp[i][j] = grid[i-1][j-1] + min(dp[i][j-1], dp[i-1][j]);
        return dp[row][col];
    }
};

 

注意到上面的代码中dp[i][j] 只和上一行的dp[i-1][j]和上一列的dp[i][j-1]有关，因此可以优化空间为O（n）（准确来讲空间复杂度可以是O（min（row,col

）））                          本文地址

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        int row = grid.size(),col;
        if(row == 0)return 0;
        else col = grid[0].size();
        vector<int >dp(col+1, INT_MAX);
        dp[1] = 0;
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= col; j++)
                dp[j] = grid[i-1][j-1] + min(dp[j], dp[j-1]);
        return dp[col];
    }
};

 

【版权声明】转载请注明出处：http://www.cnblogs.com/TenosDoIt/p/3774804.html


联系
我们