Minimum Falling Path Sum Ii - Leetcode Solution

Problem statement: Given an n x n array of integers, find the minimum sum of any falling path through the array. 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,6,9], [3,6,8], [3,5,7], [3,5,8], [3,5,9] The minimum falling path is [1,4,7], and its sum is 12.

Solution:

We can solve this problem using dynamic programming (DP) approach. In this approach, we will start from the second-last row and calculate the minimum sum of a falling path for each cell in that row. We will continue doing this for all rows until we reach the first row. Finally, we return the minimum sum of a falling path from the first row.

Let's consider the following example array:

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

We can create a DP array dp of the same size. The value of dp[i][j] will represent the minimum sum of a falling path from the element at index (i,j) to the last row.

We start from the second-last row and calculate the minimum sum of a falling path for each cell in that row. Since we can only choose elements from the next row that are in the same column or adjacent columns, we can calculate the minimum sum of a falling path for each cell as follows:

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

Here, dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1] represent the minimum sum of a falling path from the cell at (i+1,j-1), (i+1,j), (i+1,j+1) in the next row, respectively. We add arr[i][j] to these values to get the minimum sum of a falling path from the cell at (i,j) to the last row.

Finally, we return the minimum value among all dp values in the first row as the minimum sum of a falling path through the array.

Here is the implementation of the above approach in Python:

def minFallingPathSum(arr): n = len(arr) dp = [[0]*n for _ in range(n)]

# initialize the DP array with the last row
for j in range(n):
    dp[n-1][j] = arr[n-1][j]
    
# calculate the minimum sum of a falling path for each cell in the remaining rows
for i in range(n-2, -1, -1):
    for j in range(n):
        # check the possible choices for the next row
        if j == 0:
            dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + arr[i][j]
        elif j == n-1:
            dp[i][j] = min(dp[i+1][j-1], dp[i+1][j]) + arr[i][j]
        else:
            dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + arr[i][j]

# return the minimum sum of a falling path from the first row
return min(dp[0])

1