Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
652 B
0
Indexable
Never
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& mat) {
        int n=mat.size(), m=mat[0].size();
        vector<vector<int>>dp(n,vector<int>(m,0));
        dp[0]=mat[0];
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                int tu=(i>0)?dp[i-1][j]:INT_MAX;
                int tl=(i>0 && j>0)?dp[i-1][j-1]:INT_MAX;
                int tr=(i>0 && j<n-1)?dp[i-1][j+1]:INT_MAX;
                
                dp[i][j]=mat[i][j]+min(tl,min(tu,tr));
            }
        }
        int res=INT_MAX;
        for(int j=0;j<m;j++){
            res=min(res,dp[n-1][j]);
        }
        return res;
    }
};
Leave a Comment