[leetcode] 931. Minimum Falling Path Sum : https://leetcode.com/problems/minimum-falling-path-sum/

Minimum Falling Path Sum.cc

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int N = A.size();
        vector<vector<int>> d(N, vector<int>(N, 1e9));
        for(int i=0; i<N; i++) d[0][i] = A[0][i];
        
        for(int i=0; i<N-1;i++){
            for(int j=0; j<N; j++){
                if(0<j) d[i+1][j-1] = min(A[i+1][j-1] + d[i][j], d[i+1][j-1]);
                d[i+1][j] = min(A[i+1][j] + d[i][j], d[i+1][j]);
                if(j<N-1) d[i+1][j+1] = min(A[i+1][j+1] + d[i][j], d[i+1][j+1]);
            }
        }
        
        int ans = 1e9;
        for(int i=0;i<N;i++) ans = min(ans, d[N-1][i]);
        return ans;
    }
};