Minimum Falling Path Sum in C++

Suppose we have a square array of integers A, we want the minimum sum of a falling path through A. Falling path is basically a path that starts at any element in the first row, and chooses one element from each row. And the next row's element must be in a column that is different from the previous row's column by at most one. So if the matrix is like −

Then the output is 12. There are few different falling paths. these are [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9], [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,9], [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9], and the smallest sum path is [1,4,7] and sum is 12.

To solve this, we will follow these steps −

• n := size of array
• for i in range n – 2 down to 0
  • for j in range 0 to n
    • if j – 1 < 0, then x1 := inf, otherwise x1 := matrix[i + 1, j - 1]
    • x2 := matrix[i + 1, j]
    • if j + 1 >= n, then x3 := inf, otherwise x3 := matrix[i + 1, j + 1]
    • matrix[i, j] := matrix[i, j] + min of x1, x2, x3
• ans := inf
• for i in range 0 to n – 1
  • ans := min of ans and matrix[0, i]
• return ans

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int minFallingPathSum(vector<vector<int>>& a) {       int n = a.size();       for(int i =n-2;i>=0;i--){          for(int j =0;j<n;j++){             int x1 = j-1<0?INT_MAX:a[i+1][j-1];             int x2 = a[i+1][j];             int x3 = j+1>=n?INT_MAX:a[i+1][j+1];             a[i][j]+= min({x1,x2,x3});          }       }       int ans = INT_MAX;       for(int i =0;i<n;i++){          ans = min(ans,a[0][i]);       }       return ans;    } }; main(){    vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};    Solution ob;    cout <<(ob.minFallingPathSum(v)); }

Input

[[1,2,3],[4,5,6],[7,8,9]]

Output

12