Problem 931

Question statement

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix. A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Solution

The obvious approach is a 2d dp

Main idea:

Say n = len(matrix). Initialize an n x n dp array of all 0s, and the idea is to store in dp[i][j] the minimum sum of a falling path ending in index (i,j). Barring some edge cases, this then becomes a matter of setting

dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])

and return the minimum of the last row of dp.

To handle the column edge cases in a slick fashion, we use min/max functions. The row edge case of i=0 need not really be handled, because i-1 in python refers to the last row, which is all zeroes from our initialization, thus enabling dp[0][j] = matrix[0][j] for free.

Code

def minFallingPathSum(self, matrix: List[List[int]]) -> int:
    n = len(matrix)
    dp = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            dp[i][j] = matrix[i][j] + min(
                                            dp[i - 1][max(0, j - 1)], 
                                            dp[i - 1][j], 
                                            dp[i - 1][min(n - 1, j + 1)]
                                        )
    return min(dp[-1])

Comments:

Time complexity: O($n^2$).

The above code runs in 113ms beats 83.58% of users. It uses 18.27MB of memory, beating 48.96% of users.

Someone in the discussion pointed out a real life use of this problem in image compression, and it is very cool! I might make a separate post about this in side projects sometime soon. For now, check this out! Seam carving.