931. Minimum Falling Path Sum - Explanation

1. Recursion

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

        def dfs(r, c):
            if r == N:
                return 0
            if c < 0 or c >= N:
                return float("inf")
            return matrix[r][c] + min(
                dfs(r + 1, c - 1),
                dfs(r + 1, c),
                dfs(r + 1, c + 1)
            )

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

Time & Space Complexity

Time complexity: $O(3 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        N = len(matrix)
        cache = {}

        def dfs(r, c):
            if r == N:
                return 0
            if c < 0 or c >= N:
                return float("inf")
            if (r, c) in cache:
                return cache[(r, c)]
            cache[(r, c)] = matrix[r][c] + min(
                dfs(r + 1, c - 1),
                dfs(r + 1, c),
                dfs(r + 1, c + 1)
            )
            return cache[(r, c)]

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

Time & Space Complexity

Time complexity: $O(n * n)$
Space complexity: $O(n * n)$

3. Dynamic Programming (Bottom-Up)

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

        for r in range(1, N):
            leftUp = float('inf')
            for c in range(N):
                midUp = dp[c]
                rightUp = dp[c + 1] if c < N - 1 else float('inf')
                dp[c] = matrix[r][c] + min(midUp, leftUp, rightUp)
                leftUp = midUp

        return min(dp)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

4. Dynamic Programming (In-Place)

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

        for r in range(1, N):
            for c in range(N):
                mid = matrix[r - 1][c]
                left = matrix[r - 1][c - 1] if c > 0 else float("inf")
                right = matrix[r - 1][c + 1] if c < N - 1 else float("inf")
                matrix[r][c] = matrix[r][c] + min(mid, left, right)

        return min(matrix[-1])

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.