BinarySearch 0907 Minimum Dropping Path Sum

Problem statement

https://binarysearch.com/problems/Minimum-Dropping-Path-Sum/

Solution

Equal to Leetcode 1289. Minimum Falling Path Sum II.

Complexity

It is O(mn) for time and O(m) for space.

Code

class Solution:
    def solve(self, arr):
        n, m = len(arr), len(arr[0])
        dp = [0]*m
        for row in arr:
            dp2 = [0] * m
            min_ind = dp.index(min(dp))
            for i in range(m):
                if i != min_ind:
                    dp2[i] = dp[min_ind] + row[i]
                else:
                    dp2[i] = min(dp[i] for i in range(m) if i != min_ind) + row[i]       
            dp = dp2

        return min(dp)