/*
 * @lc app=leetcode.cn id=931 lang=cpp
 *
 * [931] 下降路径最小和
 */

// @lc code=start
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int best = matrix[i - 1][j];
                if (j > 0) best = min(best, matrix[i - 1][j - 1]);
                if (j < n - 1) best = min(best, matrix[i - 1][j + 1]);
                matrix[i][j] += best; 
            }
        }

        int res = INT_MAX;
        for (auto& c : matrix[m - 1]) {
            res = min(res, c);
        }
        return res;
    }
};
// @lc code=end