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

由于每次只能向右或者向下，所以可以使用如下方法：

方法一：

使用和原矩阵同等大小的dp矩阵，用以记录左上角点到当前点的最小路径和。
每一点只可能来自左或上这两个位置

#include<bits/stdc++.h>

using namespace std;

int minTraceSum(vector<vector<int>>& matrix) {
    if (matrix.empty() || matrix[0].empty())
        return 0;
    int n = matrix.size();
    int m = matrix[0].size();

    //代表左上角到当前点的最短路径和
    vector<vector<int>> dp(n, vector<int>(m));

    //左上角
    dp[0][0] = matrix[0][0];

    //左上角起的竖直行
    for (int i = 1; i < n; i++) {
        dp[i][0] = matrix[i][0] + dp[i - 1][0];
    }

    //左上角起的水平行
    for (int i = 1; i < m; i++) {
        dp[0][i] = matrix[0][i] + dp[0][i - 1];
    }
    //其余部分
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            int minV=min(dp[i-1][j],dp[i][j-1]);
            dp[i][j]=minV+matrix[i][j];
        }
    }
    return dp[n-1][m-1];
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));
    for (auto i = 0; i < n; i++) {
        for (auto j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    auto res=minTraceSum(matrix);
    cout<<res<<endl;
    return 0;
}

方法二：

压缩矩阵

#include<bits/stdc++.h>

using namespace std;

int minTraceSum(vector<vector<int>>& matrix) {
    if (matrix.empty() || matrix[0].empty())
        return 0;
    int n = matrix.size();
    int m = matrix[0].size();

    //代表左上角到当前点的最短路径和
    //dp仅一层，起始时为[0][0]点到[0][j]点的最短路径和，
    //终止时为[0][0]点到[n-1][j]点的最短路径和
    //即不断滚动更新
    vector<int> dp(m);
    //起始时，第一行
    dp[0] = matrix[0][0];
    for (int j = 1; j < m; j++) {
        dp[j] = dp[j - 1] + matrix[0][j];
    }

    //后面的行
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //每行起始第一个，即[i][0]
            if (j == 0) {
                //未更新前的dp[j]代表上一行j位置的最短路径和
                dp[j] += matrix[i][j];
            } else {
                //dp[j-1]代表左侧位置，即[0][0]到[i-1][j]处的最短路径和
                //此处的dp[j]还未更新，代表[0][0]到[i][j-1]处的最短路径和
                //取最小值为了判断是从左边还是从上边来时路径和更小
                dp[j] = min(dp[j-1],dp[j])+matrix[i][j];
            }
        }
    }
    return dp[m-1];
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));
    for (auto i = 0; i < n; i++) {
        for (auto j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    auto res = minTraceSum(matrix);
    cout << res << endl;
    return 0;
}