BinarySearch 0908 Minimum Dropping Path Sum With Column Distance Constraint

Problem statement

https://binarysearch.com/problems/Minimum-Dropping-Path-Sum-With-Column-Distance-Constraint/

Solution

Equal to Leetcode 0931. Minimum Falling Path Sum.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, M):
        n, m = len(M), len(M[0])
        @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 < m-1: ans = min(ans, dp(i - 1, j + 1))
            return ans + M[i][j]
        
        return min(dp(n-1, x) for x in range(m))