<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 get_min_two(row):
            two_smallest = []  # (val, idx)
            for val, idx in row:
                if len(two_smallest) < 2:
                    two_smallest.append((val, idx))
                    two_smallest.sort()
                elif two_smallest[1][0] >  val:
                    two_smallest.pop()
                    two_smallest.append((val, idx))
                two_smallest.sort()
            return two_smallest

        N = len(grid)
        first_row = [(val, idx) for idx, val in enumerate(grid[0])]
        dp = get_min_two(first_row)
        for r in range(1, N):
            next_dp = []  # val, idx
            for curr_c in range(N):
                cur_val = grid[r][curr_c]
                min_val = float("inf")
                for prev_val, prev_c in dp:  # this is len 2
                    if curr_c != prev_c:
                        min_val = min(
                            min_val, cur_val + prev_val)
                next_dp.append((min_val, curr_c))
                next_dp = get_min_two(next_dp)
            dp = next_dp
        return min([val for val, idx in dp])

        # dp
        N = len(grid)
        dp = grid[0]
        for r in range(1, N):
            next_dp = [float("inf")] * N
            for curr_c in range(N):
                for prev_c in range(N):
                    if prev_c != curr_c:
                        next_dp[curr_c] = min(
                            next_dp[curr_c],
                            grid[r][curr_c] + dp[prev_c]
                        )
            dp = next_dp
        return min(dp)

        # memoization
        cache = {}

        def helper(r, c):
            if r == N - 1:
                return grid[r][c]
            if (r, c) in cache:
                return cache[(r, c)]
            
            res = float("inf")
            for next_col in range(N):
                if c != next_col:
                    res = min(
                        res,
                        grid[r][c] + helper(r + 1, next_col)
                    )
            
            cache[(r, c)] = res
            return cache[(r, c)]
        
        res = float("inf")
        for c in range(N):
            res = min(res, helper(0, c))
        return res

        # my sol 
        # dp
        ROWS, COLS = len(grid), len(grid[0])
        # dp = [[float("inf")] * COLS for _ in range(ROWS)]
        # for c in range(COLS):
        #     dp[0][c] = grid[0][c]
        dp = grid[0][:]

        for r in range(1, ROWS):
            newdp = [float("inf")] * COLS
            for c in range(COLS):
                val = float("inf")
                for pc in range(COLS):
                    if pc == c:
                        continue
                    val = min(val, dp[pc])
                newdp[c] = grid[r][c] + (val if val != float("inf") else 0)
            dp = newdp

        return min(dp)

        # memoization
        ROWS, COLS = len(grid), len(grid[0])
        cache = {}

        def dfs(r, c):
            # if c < 0 or c == COLS:
            #     return float("-inf")
            if (r, c) in cache:
                return cache[(r, c)]
            if r == ROWS:
                return 0

            res = float("inf")
            for nc in range(COLS):
                if nc == c:
                    continue
                res = min(res, dfs(r + 1, nc))
        
            cache[(r, c)] = grid[r][c] + (res if res != float("inf") else 0)
            return cache[(r, c)]
        
        ret = float("inf")
        for fc in range(COLS):
            ret = min(ret, dfs(0, fc))
        return ret

20300