Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

&nbsp;
Example 1:

Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is&nbsp;[1,5,7], so the answer is&nbsp;13.


Example 2:

Input: grid = [[7]]
Output: 7


&nbsp;
Constraints:


	n == grid.length == grid[i].length
	1 &lt;= n &lt;= 200
	-99 &lt;= grid[i][j] &lt;= 99


class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if m == 1 and n == 1:
            return grid[0][0]
        min_arr = [0 for _ in range(n)]
        for i in range(m):
            prefix = [float('inf') for _ in range(n)]
            suffix = [float('inf') for _ in range(n)]
            current_row = [elem1+elem2 for elem1, elem2 in zip(grid[i], min_arr)]
            for i in range(1, n):
                prefix[i] = min(prefix[i-1], current_row[i-1])
            for i in range(n-2, -1, -1):
                suffix[i] = min(suffix[i+1], current_row[i+1])
            min_arr = [min(pre, suff) for pre, suff in zip(prefix, suffix)]
        return min(min_arr)
class Solution {
    // Recursion
   /* public int minFallingPathSum(int[][] grid) {
        int n=grid.length;
        if(n==1) return grid[0][0];
        int ans = 10000000;
        for(int i=0 ; i<n ; i++){
            ans = Math.min(ans , grid[0][i] + helper(grid , n , 1 , i));
        }
        return ans;
    }
    
    private int helper(int[][] grid , int n , int i , int last){
        if( i == n-1 ){
            int min = 100;
            for(int k=0 ; k<n ; k++){
                if(k!=last){
                    min = Math.min( grid[n-1][k] , min);
                }
            }
            return min;
        }
        
        int min = 100000000;
        for(int k=0 ; k<n ; k++){
            if(k != last){
                min = Math.min( min ,grid[i][k] +  helper(grid , n , i+1 , k) );
            }
        }
        
        return min;
    }
    */
    
    // DP MEMOIZATION
    public int minFallingPathSum(int[][] grid) {
        int n=grid.length;
        if(n==1) return grid[0][0];
        int[][] dp = new int[n][n];
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<n ; j++){
                dp[i][j] = -1;
            }
        }
        
        int ans = 10000000;
        for(int i=0 ; i<n ; i++){
            ans = Math.min(ans , grid[0][i] + helper(grid , n , 1 , i , dp));
        }
        return ans;
    }
    
    private int helper(int[][] grid , int n , int i , int last , int[][] dp){
        if( i == n-1 ){
            int min = 100;
            for(int k=0 ; k<n ; k++){
                if(k!=last){
                    min = Math.min( grid[n-1][k] , min);
                }
            }
            return min;
        }
        if(dp[i][last] != -1) return dp[i][last];
        int min = 100000000;
        for(int k=0 ; k<n ; k++){
            if(k != last){
                min = Math.min( min ,grid[i][k] +  helper(grid , n , i+1 , k , dp) );
            }
        }
        
        dp[i][last] = min;
        return dp[i][last];
    }
}
class Solution {
public:

    int f(int i, int j, vector<vector<int>> &matrix, vector<vector<int>> &dp){

        //to handle edge cases if the j index is less than 0 or greater than size of the array.
        if(j<0 or j>=matrix[0].size()) return 1e8;

        //base case
        if(i==0) return dp[0][j] = matrix[0][j];

        if(dp[i][j]!=-1) return dp[i][j];

        int ans = INT_MAX;

         //Here we have to iterate through all the possiblities in the entire upper row for each
         //element except for the element which is directly above the current element in the
         //matrix, and then we have to find the minimum.
        for(int k=0;k<matrix[0].size();k++){
            if(k==j) continue;
            ans = min(ans, matrix[i][j] + f(i-1, k, matrix, dp));
        }

        return dp[i][j] = ans;

    }

    int minFallingPathSum(vector<vector<int>>& grid) {

        int mini = INT_MAX;
        int n = grid.size();

        vector<vector<int>> dp(n, vector<int>(n,-1));

        for(int j=0;j<n;j++){

            mini = min(mini, f(n-1, j, grid, dp));

        }

        return mini;

    }
};
var minFallingPathSum = function(grid) {
if(grid.length===1){
    return grid[0][0];
}
let sums = [];//find first, second and third minimum values in the grid as these are only possible values for path
//store the index for fast lookup in a 3D array
for(let i=0; i<grid.length; i++){
    let min = Math.min(...grid[i]);
    let idx = grid[i].indexOf(min);
    grid[i].splice(idx, 1, Infinity);
    let min2 = Math.min(...grid[i]);
    let idx2 = grid[i].indexOf(min2);
    grid[i].splice(idx2, 1, Infinity);
    let min3 = Math.min(...grid[i]);
    let idx3 = grid[i].indexOf(min3);
    sums.push([[min,idx],[min2,idx2],[min3,idx3]]);
}
// sums contains 1st , 2nd and 3rd min value and index
let memo = {}; // for memoization
let recur = (r,li) => {//recursive call to decide which path to choose from r=row, li=lastIndex
    if(memo[r+','+li] !== undefined){// memoized
        return memo[r+','+li];
    }
    if(r===grid.length-1){// last and first choice for path can only be from 1st and 2nd minimum, as there is only one other row to occupy these columns
        if(li===sums[r][0][1]){
            memo[r+','+li] = sums[r][1][0];
        }
        else{
            memo[r+','+li] = sums[r][0][0];
        }
        return memo[r+','+li];
    }
    else{
        switch (li) {// pick the minimum value path where index is not equal to last index
            case sums[r][0][1]:
                memo[r+','+li] = Math.min(sums[r][1][0]+recur(r+1,sums[r][1][1]),sums[r][2][0]+recur(r+1,sums[r][2][1]));
                break;
            case sums[r][1][1]:
                memo[r+','+li] = Math.min(sums[r][0][0]+recur(r+1,sums[r][0][1]),sums[r][2][0]+recur(r+1,sums[r][2][1]));
                break;
            case sums[r][2][1]:
                memo[r+','+li] = Math.min(sums[r][1][0]+recur(r+1,sums[r][1][1]),sums[r][0][0]+recur(r+1,sums[r][0][1]));
                break;
            default:
                memo[r+','+li] = Math.min(sums[r][0][0]+recur(r+1,sums[r][0][1]),sums[r][1][0]+recur(r+1,sums[r][1][1]),sums[r][2][0]+recur(r+1,sums[r][2][1]));
        }
        return memo[r+','+li];
    }
}
return recur(0,sums[0][2][1]);//since first and last can only be picked from 1st and 2nd min values
};
Minimum Falling Path Sum II