Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

&nbsp;
Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.


Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.


&nbsp;
Constraints:


	n == matrix.length == matrix[i].length
	1 &lt;= n &lt;= 100
	-100 &lt;= matrix[i][j] &lt;= 100


class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        for row in range(1, len(matrix)):
            for col in range(0, len(matrix[row])):
                if col == 0:
                    matrix[row][col] += min(matrix[row-1][col+1], matrix[row-1][col])
                elif col == len(matrix[row]) - 1:
                    matrix[row][col] += min(matrix[row-1][col-1], matrix[row-1][col])
                else:
                    matrix[row][col] += min(matrix[row-1][col-1], matrix[row-1][col], matrix[row-1][col+1])
                
        return min(matrix[-1])
class Solution {
    public int min(int[][] matrix, int[][]dp, int i, int j)
    {
        int a,b,c;
        if(i==0)
            return matrix[i][j];
        if(dp[i][j] != Integer.MAX_VALUE)
            return dp[i][j];
        if(j==0)
        {
            dp[i][j] = Math.min(min(matrix, dp, i-1,j),min(matrix, dp, i-1, j+1))+matrix[i][j];
        }
        else if(j==matrix.length -1)
        {
            dp[i][j] = Math.min(min(matrix, dp, i-1,j),min(matrix, dp, i-1, j-1))+matrix[i][j];
        }
        else
        {
            dp[i][j] = Math.min(Math.min(min(matrix, dp, i-1,j),min(matrix, dp, i-1, j+1)),min(matrix, dp, i-1, j-1))+matrix[i][j];
        }
        return dp[i][j];
    }

    public int minFallingPathSum(int[][] matrix) {
        int dp[][] = new int[matrix.length][matrix.length];
        if(matrix.length == 1)
            return matrix[0][0];
        for(int i=0;i<matrix.length;i++)
            for(int j=0;j<matrix.length;j++)
                dp[i][j] = Integer.MAX_VALUE;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<matrix.length; i++)
        {
            min = Math.min(min, min(matrix, dp, matrix.length-1,i));
        }
        return min;
    }
}
class Solution {
public:
    
    int check( int i , int j , int n  ){
        if( i <0  || j<0 || i>=n || j>=n )
            return 0;
        return 1;
    }
    
    int solve(vector<vector<int>>&mat , int i , int j  , int n , vector<vector<int>>&dp ){
        
        if(not check( i , j , n ))
            return 999999;
        
        if(i == n-1 && j < n  )return mat[i][j];
        
        if(dp[i][j]!= -1 )
            return dp[i][j];
        
        
        int op_1 = mat[i][j] + solve(mat , i+1,  j - 1 , n , dp );
        int op_2 = mat[i][j] + solve(mat , i+1 , j  ,    n , dp );
        int op_3 = mat[i][j] + solve(mat , i+1 , j + 1 , n , dp );
        
        
        return dp[i][j] =  min( {op_1 , op_2 , op_3} );
        
        
    }
    
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix[0].size();
        
//         vector<vector<int>>dp(n+1 , vector<int>(n +1 , -1 ));
//         int ans =  INT_MAX;
//         for(int i = 0  ; i<n ; ++i )
//             ans = min( ans , solve( matrix , 0, i , n , dp ));
        
        
        
        vector<vector<int>>dp(n , vector<int>(n, 0));
        for( int i =0  ; i<n ; ++i )
            dp[0][i] = matrix[0][i];
        
        
        for( int i =1 ; i<n ; ++i ){
            for( int j = 0  ; j<n ; ++j ){
                
                if(j-1>=0 && j+1 < n )
                    dp[i][j] = matrix[i][j] + min( {dp[i-1][j-1] ,  dp[i-1][j] , dp[i-1][j+1] });
                else if(j == 0 )
                     dp[i][j] = matrix[i][j] + min( { dp[i-1][j] , dp[i-1][j+1] });
                else if(j == n-1 )
                     dp[i][j] = matrix[i][j] + min( {dp[i-1][j-1] ,  dp[i-1][j] });
            }
        }
        
        int ans = INT_MAX;
        for( int i = 0  ; i<n ; ++i )
            ans = min( ans , dp[n-1][i]);
        
        
        
        
        return ans ;
    }
};
var minFallingPathSum = function(matrix) {
    let n = matrix.length;
    let m = matrix[0].length;
    let dp = new Array(n).fill(0).map(() => new Array(m).fill(0));
    
    // tabulation // bottom-up approach
    
    // base case - when i will be 0, dp[0][j] will be matrix[0][j]
    for(let j = 0; j < m; j++) dp[0][j] = matrix[0][j]
    
    for(let i = 1; i < n; i++) {
        for(let j = 0 ; j < m; j++) {
            let up = matrix[i][j] + dp[i - 1][j];
            
            let upLeft = matrix[i][j];
            if((j - 1) >= 0) upLeft += dp[i - 1][j - 1]; // if not out of bound
            else upLeft += 10000; // big enough number
            
            let upRight = matrix[i][j];
            if((j + 1) < m) upRight += dp[i - 1][j + 1]; // if not out of bound
            else upRight += 10000; // big enough number
            
            dp[i][j] = Math.min(up, upLeft, upRight);
        }
    }
    return Math.min(...dp[n - 1]);
};
Minimum Falling Path Sum