Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
795 B
0
Indexable
Never
class Solution {
public:
    long long solve(int x,int y,vector<vector<int>>&mat,vector<vector<int>>&dp){
        if(x<0 || x>=mat.size() || y<0 || y>=mat[0].size()) return INT_MAX;
        if(x==mat.size()-1) return mat[x][y];

        if(dp[x][y]!=-1) return dp[x][y];

        long long dd=mat[x][y],dl=mat[x][y],dr=mat[x][y];
        dd+=solve(x+1,y,mat,dp);
        dl+=solve(x+1,y-1,mat,dp);
        dr+=solve(x+1,y+1,mat,dp);

        return dp[x][y]=min(dd,min(dr,dl));
    }



    int minFallingPathSum(vector<vector<int>>& mat) {
        long long res=INT_MAX;
        vector<vector<int>>dp(mat.size(),vector<int>(mat[0].size(),-1));
        for(int i=0;i<mat[0].size();i++){
            res=min(res,solve(0,i,mat,dp));
        }
        return res;
    }
};
Leave a Comment