Minimum Falling Path Sum

931. Minimum Falling Path Sum


1   2  3   4  ------------- 1   2   3   4
4  -1  3  -2  ------------- 5   0   5   1
-2  5  -3  2  ------------- -2  4  -3  3
7   -6  9  8  ------------- 5   -9  6   5
minimun element = -9.
time complexity = O(n^2)

Code:


//#include<bits/stdc++.h>
using vi = vector<int>;
using vvi = vector<vi>:

int minFallingpathsum(vector<vector>>& a){
    int n =a.size();
    vvi dp(n,vi(n));
    dp[0] = a[0];
    for(int i = 1; i < n; i++){
        for(int j = 0; j < n; j++){
            dp[i][j] = a[i][j] + dp[i-1][j];
            if(j > 0)
                dp[i][j] = min(dp[i][j], a[i][j]+dp[i-1][j-1]);
            if(j < n- 1)dp[i][j] = min(dp[i][j], dp[i-1][j+1]);
        }
    }
    return *min_element(dp[n-1].begin(), dp[n-1].end());
}

Share: