<p>Given an <code>n x n</code> integer matrix <code>grid</code>, return <em>the minimum sum of a <strong>falling path with non-zero shifts</strong></em>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/falling-grid.jpg" style="width: 244px; height: 245px;" />
<pre>
<strong>Input:</strong> grid = [[1,2,3],[4,5,6],[7,8,9]]
<strong>Output:</strong> 13
<strong>Explanation:</strong> 
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[7]]
<strong>Output:</strong> 7
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 200</code></li>
	<li><code>-99 &lt;= grid[i][j] &lt;= 99</code></li>
</ul>

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            nonlocal dp, m, n

            # base1; last row so return the cell value
            if i == m - 1:
                return grid[i][j]

            # seen before
            if dp[i][j] != -1:
                return dp[i][j]

            # otherwise compute dp[i][j]
            res = float('inf')
            for col in range(n):
                # pass; same column as j
                if col == j:
                    continue

                # get the current cell value and go to next row i + 1
                temp = grid[i][j] + dfs(i + 1, col)

                # compare
                res = min(res, temp)

            # update
            dp[i][j] = res

            return dp[i][j]

        m, n = len(grid), len(grid[0])

        # dp[i][j] := minimum sum of a falling path with non-zero shifts starting at cell (i, j)
        dp = [[-1 for _ in range(n)] for _ in range(m)]

        minSum = float('inf')

        # run dfs for each possible col on first row
        for j in range(n):
            temp = dfs(0, j)
            minSum = min(minSum, temp)

        return minSum
        # @cache
        # def f(i, j):
        #     if i != len(g):
        #         return min(v + f(i+1, q) for q,v in enumerate(g[i]) if q != j)

        #     return 0
        
        # return f(0, -1)


        
        # # n is the length of matrix
        # n=len(matrix)
        # # make dp and and fill it with 0 
        # dp = [[0 for i in range(n)] for i in range(n)]
        # # if col and row size is 1 
        # if len(matrix[0]) == 1 and len(matrix) == 1:
        #     return matrix[0][0]
        # # for col
        # for j in range(len(matrix[0])):
        #     dp[0][j] = matrix[0][j]
        # # now, we have many choices for column except adjacent element in same column
        # for i in range(1, len(matrix)):
        #     for j in range(0,len(matrix[0])):
        #         minimum = math.inf
        #         for col in range(len(matrix[0])):      
        #             # we can't consider the adjacent element in 
        #             # same column
        #             if col != j: 
        #                 min_path = matrix[i][j]  + dp[i-1][col]
        #                 #take min of prev min and current min_path
        #                 minimum = min(minimum, min_path)
        #         dp[i][j] = minimum
        # return min(dp[len(matrix)-1])

        
    
22500