Minimum sum falling path in a NxN grid in C++

Problem statement

• Given a matrix A of integers of size NxN. The task is to find the minimum sum of a falling path through A.
• A falling path will start at any element in the first row and ends in last row.
• It chooses one element from each next row. The next row’s choice must be in a column that is different from the previous row’s column by at most ones

Example

If N = 2 and matrix is: {    {5, 10},    {25, 15} } then output will be 20 as element 5 and 15 are selected

Example

 Live Demo

#include <bits/stdc++.h> #define MAX 2 using namespace std; int getMinSumPath(int matrix[MAX][MAX]) {    for (int row = MAX - 2; row >= 0; --row) {       for (int col = 0; col < MAX; ++col) {          int val = matrix[row + 1][col];          if (col > 0) {             val = min(val, matrix[row +1][col - 1]);          }          if (col + 1 < MAX) {             val = min(val, matrix[row +1][col + 1]);          }          matrix[row][col] = matrix[row][col] +val;       }    }    int result = INT_MAX;    for (int i = 0; i < MAX; ++i)    result = min(result, matrix[0][i]);    return result; } int main() {    int matrix[MAX][MAX] = {       {5, 10},       {25, 15},    };    cout << "Minimum sum path = " << getMinSumPath(matrix)    << endl;    return 0; }

When you compile and execute above program. It generates following output

Output

Minimum sum path = 20