题解 | 矩阵的最小路径和

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

        // int m = matrix.size(), n = matrix[0].size();
        // vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        // dp[0][1] = 0;
        // for (int i = 0; i < m; i++) {
        //     for (int j = 0; j < n; j++) {
        //         dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j]) + matrix[i][j];
        //     }
        // }
        // return dp[m][n];
    }
};