Leetcode 0931. Minimum Falling Path Sum

Problem statement

https://leetcode.com/problems/minimum-falling-path-sum/

Solution

Classical dp problem, similar to robot paths.

Complexity

It is O(n^2) for time and space.

Code

class Solution:
    def minFallingPathSum(self, M):
        n = len(M)
        @lru_cache(None)
        def dp(i, j):
            if i == 0: return M[0][j]
            ans = dp(i - 1, j)
            if j > 0: ans = min(ans, dp(i - 1, j - 1))
            if j < n-1: ans = min(ans, dp(i - 1, j + 1))
            return ans + M[i][j]
        
        return min(dp(n-1, x) for x in range(n))