56

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to recursively find the 
    minimum path sum for a given cell*/
    int func(int i, int j, int m, vector<vector<int>> &matrix) {
        // Base Conditions
        if (j < 0 || j >= m)
            return 1e9; 
        if (i == 0)
            return matrix[0][j]; 
    
        /* Calculate the minimum path sum by 
        considering three possible directions:
        up, left diagonal, and right diagonal*/
        int up = matrix[i][j] + func(i - 1, j, m, matrix);
        int leftDiagonal = matrix[i][j] + func(i - 1, j - 1, m, matrix);
        int rightDiagonal = matrix[i][j] + func(i - 1, j + 1, m, matrix);
    
        // Return the minimum of the three paths 
        return min(up, min(leftDiagonal, rightDiagonal));
}
public:
    /* Function to find the minimum
    path sum in the given matrix*/
    int minFallingPathSum(vector<vector<int>> &matrix) {
        int n = matrix.size(); 
        int m = matrix[0].size(); 
    
        int mini = INT_MAX; 
    
        /* Iterate through each cell in the first row 
        to find minimum path sum starting from each of them*/
        for (int j = 0; j < m; j++) {
            int ans = func(n - 1, j, m, matrix); 
            mini = min(mini, ans); 
        }
        // Return the minimum path sum
        return mini; 
    }
};

int main() {
    vector<vector<int>> matrix{{1, 2, 10, 4}, {100, 3, 2, 1}, {1, 1, 20, 2}, {1, 2, 2, 1}};
    
    //Create an instance of Solution class
    Solution sol;
    
    // Call the getMinPathSum function and print the result
    cout << sol.minFallingPathSum(matrix) << endl;

    return 0;
}

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556

import java.util.*;

class Solution {
    /* Function to recursively find the
    minimum path sum for a given cell*/
    private int func(int i, int j, int m, int[][] matrix) {
        // Base Conditions
        if (j < 0 || j >= m)
            return (int) 1e9; 
        if (i == 0)
            return matrix[0][j]; 
    
        /* Calculate the minimum path sum by 
        considering three possible directions:
        up, left diagonal, and right diagonal*/
        int up = matrix[i][j] + func(i - 1, j, m, matrix);
        int leftDiagonal = matrix[i][j] + func(i - 1, j - 1, m, matrix);
        int rightDiagonal = matrix[i][j] + func(i - 1, j + 1, m, matrix);
    
        // Return the minimum of the three paths 
        return Math.min(up, Math.min(leftDiagonal, rightDiagonal));
    }

    // Function to find the minimum path sum in given matrix
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
    
        int mini = Integer.MAX_VALUE;
    
        /* Iterate through each cell in the first row to 
        find minimum path sum starting from each of them*/
        for (int j = 0; j < m; j++) {
            int ans = func(n - 1, j, m, matrix);
            m