1289. Minimum Falling Path Sum II - Explanation

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        N = len(grid)

        def helper(r, c):
            if r == N - 1:
                return grid[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))
            return res

        res = float("inf")
        for c in range(N):
            res = min(res, helper(0, c))
        return res

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        N = len(grid)
        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 res

        res = float("inf")
        for c in range(N):
            res = min(res, helper(0, c))
        return res

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        N = len(grid)
        dp = [[float("inf")] * N for _ in range(N)]

        for c in range(N):
            dp[N - 1][c] = grid[N - 1][c]

        for r in range(N - 2, -1, -1):
            for c in range(N):
                for next_col in range(N):
                    if c != next_col:
                        dp[r][c] = min(dp[r][c], grid[r][c] + dp[r + 1][next_col])

        return min(dp[0])

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        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)

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        def get_min_two(row):
            two_smallest = []
            for val, idx in row:
                if len(two_smallest) < 2:
                    two_smallest.append((val, idx))
                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 = []
            for curr_c in range(N):
                curr_val = grid[r][curr_c]
                min_val = float("inf")
                for prev_val, prev_c in dp:
                    if curr_c != prev_c:
                        min_val = min(min_val, curr_val + prev_val)
                next_dp.append((min_val, curr_c))
            dp = get_min_two(next_dp)

        return min(val for val, idx in dp)

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 1:
            return grid[0][0]

        dp_idx1 = dp_idx2 = -1
        dp_val1 = dp_val2 = 0

        for i in range(n):
            nextDp_idx1 = nextDp_idx2 = -1
            nextDp_val1 = nextDp_val2 = float("inf")

            for j in range(n):
                cur = dp_val1 if j != dp_idx1 else dp_val2
                cur += grid[i][j]

                if nextDp_idx1 == -1 or cur < nextDp_val1:
                    nextDp_idx2, nextDp_val2 = nextDp_idx1, nextDp_val1
                    nextDp_idx1, nextDp_val1 = j, cur
                elif nextDp_idx2 == -1 or cur < nextDp_val2:
                    nextDp_idx2, nextDp_val2 = j, cur

            dp_idx1, dp_idx2, dp_val1, dp_val2 = nextDp_idx1, nextDp_idx2, nextDp_val1, nextDp_val2

        return dp_val1