Minimum Falling Path Sum - Leetcode Solution

Problem:

Given a square grid of integers, find the minimum sum of the falling path through the grid.

A falling path starts at any element in the first row and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.

Example:

Input:

[[1,2,3], [4,5,6], [7,8,9]]

Output: 12

Explanation:

The possible falling paths are:

[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9], [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [3,5,7], [3,5,8], [3,5,9]

The minimum falling path is [1,4,7] which has a sum of 12.

Solution:

This is a dynamic programming problem. We can define dp[i][j] as the minimum possible sum of a falling path starting at (i, j).

We can initialize dp[0][j]=grid[0][j] for all j=0 to n-1.

Then, for each i=1 to n-1, we consider all possible paths that end at (i,j) and choose the one that has minimum sum. The possible paths are starting from (i-1,j-1), (i-1,j) and (i-1,j+1) if they exist.

Therefore, the recurrence relation is dp[i][j]=grid[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]).

Finally, the answer is min(dp[n-1][j]) for all j=0 to n-1.

Time Complexity:

The time complexity of the algorithm is O(n^2) where n is the size of the grid.

Space Complexity:

The space complexity of the algorithm is also O(n^2) where n is the size of the grid.

Code:

Here is the code in Python:

class Solution: def minFallingPathSum(self, grid: List[List[int]]) -> int: n = len(grid) dp = [[0] * n for _ in range(n)] for j in range(n): dp[0][j] = grid[0][j] for i in range(1, n): for j in range(n): dp[i][j] = grid[i][j] + min( dp[i-1][j-1] if j > 0 else float("inf"), dp[i-1][j], dp[i-1][j+1] if j < n-1 else float("inf") ) return min(dp[n-1])

1