Problem statement

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

Solution

Actually this is the same problem as 0265 Paint House II.

Complexity

Time complexity is O(n^2), space is O(n)

Code

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