class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        auto dp = matrix;
        int len = matrix.size();
        for (int i = 1; i < len; i++) {
            dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + dp[i][0];
            for (int j = 1; j < len - 1; j++) {
                dp[i][j] += min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1]));
            }
            dp[i][len-1] += min(dp[i-1][len-2], dp[i-1][len-1]);
        }
        int ret = dp[len-1][0];
        for (int i = 1; i < len; i++)
            ret = ret < dp[len-1][i] ? ret : dp[len-1][i];
        return ret;
    }
};