题解 | #矩阵的最小路径和#

方法：动态规划

1、遍历该矩阵的所有位置，使用一个二维数组dp记录不同位置为终点时的最小路径和，可以得到如下的状态方程：

不处于第一行和第一列：dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i][j - 1])

处于第一列不处于第一行：dp[i][j] = matrix[i][j] + dp[i - 1][j]

处于第一行不处于第一列：dp[i][j] = matrix[i][j] + dp[i][j - 1]

处于第一行且处于第一列：dp[i][j] = matrix[i][j]

2、二维数组的右下角元素即为矩阵的最小路径和

时间复杂度：o(nm)

空间复杂度：o(nm)

class Solution {
  public:
    int minPathSum(vector<vector<int> >& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        // 使用二维数组记录不同位置为终点时的最小路径和
        vector<vector<int> > dp(n, vector<int> (m, 0));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 在边界位置的要特殊处理
                if (i > 0 && j > 0)
                    dp[i][j] = matrix[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
                else if (i > 0)
                    dp[i][j] = matrix[i][j] + dp[i - 1][j];
                else if (j > 0)
                    dp[i][j] = matrix[i][j] + dp[i][j - 1];
                else
                    dp[i][j] = matrix[i][j];
            }
        }
        // 返回二维数组右下角元素
        return dp[n - 1][m - 1];
    }
};

本题还可以直接使用原矩阵来存储不同位置为终点时的最小路径和，不需要额外的辅助空间，能进一步节省空间。