class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        auto dp = grid;
        int len = grid.size();
        for (int i = 1; i < len; i++) {
            int min1 = min(dp[i-1][0], dp[i-1][1]), min2 = max(dp[i-1][0], dp[i-1][1]);
            for (int j = 2; j < len; j++) {
                if (dp[i-1][j] < min1) min2 = min1, min1 = dp[i-1][j];
                else if (dp[i-1][j] == min1) min2 = min1;
                else if (dp[i-1][j] < min2) min2 = dp[i-1][j];
            }
            for (int j = 0; j < len; j++) {
                if (dp[i-1][j] == min1) dp[i][j] += min2;
                else dp[i][j] += min1;
            }
        }
        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;
    }
};