64. Minimum Path Sum.md

64. Minimum Path Sum

思路

给定一个m x n的矩阵，从左上角走到右下角，求最小路径和。就是一个简单的动态规划：

dp[i][j] 代表从 grid[0][0] 走到 grid[i][j] 的最小路径和。

因为只能往下或者往右走，所以状态更新方程为

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

可以利用滚动数组的方式将空间复杂度优化到O(n)或者O(m)。

值得一提的是如果给定的矩阵grid可写的话我们可以就将其作为dp数组，这样就不用额外的空间了。

C++

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

滚动数组空间优化

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