Untitled
unknown
plain_text
a year ago
652 B
4
Indexable
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; } };
Editor is loading...
Leave a Comment