LC1289. Minimum Falling Path Sum II

Approach 1: Dynamic Programming, Top-Down

from functools import lru_cache
 
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
 
        if n == 1:
            return grid[0][0]
 
        @lru_cache(None)
        def findMinSize(r, c):
            if r >= n:
                return 0
            
            res = float("inf")
            for oc in range(n):
                if c != oc:
                    res = min(res, grid[r][c] + findMinSize(r + 1, oc))
            
            return res
        
        res = float("inf")
        for c in range(n):
            res = min(res, findMinSize(0, c))
 
        return res

Complexity

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

Approach 2: Dynamic Programming, Bottom-Up

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        dp = grid[0]
        n = len(grid)
        
        for row in range(1, n):
            next_dp = [sys.maxsize for _ in range(n)]
 
            for col in range(n):
                for other_col in range(n):
                    if col != other_col:
                        next_dp[col] = min(next_dp[col], grid[row][col] + dp[other_col])
            
            dp = next_dp
        
        return min(dp)

Complexity

Time: $O(n^3)$
Space: $O(n)$

Other Languages