Solution For Minimum Falling Path Sum

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])

Step by Step Implementation For Minimum Falling Path Sum

class Solution {
    public int minFallingPathSum(int[][] A) {
        // DP solution
        // dp[i][j] represents the minimum falling path sum from A[i][j]
        int n = A.length;
        int[][] dp = new int[n][n];
        
        // base case: dp[0][j] = A[0][j]
        for (int j = 0; j < n; j++) {
            dp[0][j] = A[0][j];
        }
        
        // bottom-up
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // find the minimum of the three adjacent numbers
                int min = A[i][j];
                if (j - 1 >= 0) {
                    min = Math.min(min, A[i][j - 1]);
                }
                if (j + 1 < n) {
                    min = Math.min(min, A[i][j + 1]);
                }
                // update dp[i][j]
                dp[i][j] = dp[i - 1][j] + min;
            }
        }
        
        // return the minimum of dp[n - 1][j]
        int min = dp[n - 1][0];
        for (int j = 1; j < n; j++) {
            min = Math.min(min, dp[n - 1][j]);
        }
        return min;
    }
}

def minimumFallingPathSum(A):
    
    # define dp array
    dp = [[0 for i in range(len(A))] for j in range(len(A))]
    
    # base case
    for i in range(len(A)):
        dp[0][i] = A[0][i]
        
    # fill up dp array
    for i in range(1, len(A)):
        for j in range(len(A)):
            
            # find the minimum of the 3 adjacent values in the previous row
            min_adj = dp[i-1][j]
            if j > 0:
                min_adj = min(min_adj, dp[i-1][j-1])
            if j < len(A)-1:
                min_adj = min(min_adj, dp[i-1][j+1])
                
            # update the current value in the dp array
            dp[i][j] = A[i][j] + min_adj
            
    # find and return the minimum value in the last row of the dp array
    min_path = dp[-1][0]
    for i in range(1, len(A)):
        min_path = min(min_path, dp[-1][i])
        
    return min_path

/**
 * @param {number[][]} A
 * @return {number}
 */
var minFallingPathSum = function(A) {
    // Base case: if A is only one row, then the min falling path sum is just the min value in that row
    if (A.length === 1) {
        return Math.min(...A[0]);
    }
    
    // Iterate through each row of A, starting from the second to last row
    for (let i = A.length - 2; i >= 0; i--) {
        // Iterate through each element in row i
        for (let j = 0; j < A[i].length; j++) {
            // For each element, find the min of the element directly below it, and the two adjacent elements below it
            let min = A[i+1][j];
            if (j > 0) {
                min = Math.min(min, A[i+1][j-1]);
            }
            if (j < A[i].length - 1) {
                min = Math.min(min, A[i+1][j+1]);
            }
            // Add the min value to the current element to get the min falling path sum
            A[i][j] += min;
        }
    }
    
    // Return the min value in the first row, which will be the min falling path sum
    return Math.min(...A[0]);
};

int minFallingPathSum(vector>& A) {
        int N = A.size();
        for (int r = N-2; r >= 0; --r) {
            for (int c = 0; c < N; ++c) {
                int best = A[r+1][c];
                if (c > 0)
                    best = min(best, A[r+1][c-1]);
                if (c+1 < N)
                    best = min(best, A[r+1][c+1]);
                A[r][c] += best;
            }
        }

        return *min_element(A[0].begin(), A[0].end());
    }

using System; 

public class Solution {
    public int MinFallingPathSum(int[][] A) {
        // DP solution where dp[i][j] represents the minimum 
        // falling path sum from A[i][j] 
        int N = A.Length; 
        int[][] dp = new int[N][]; 
        for (int i = 0; i < N; i++) 
            dp[i] = new int[N]; 
          
        // Base cases 
        for (int i = 0; i < N; i++) 
            dp[0][i] = A[0][i]; 
          
        for (int i = 1; i < N; i++) 
        { 
            for (int j = 0; j < N; j++) 
            { 
                // Find minimum from 3 possible paths 
                // and add to current cell's value 
                if (j == 0) 
                    dp[i][j] = A[i][j] + Math.Min(dp[i - 1][j],  
                                                 dp[i - 1][j + 1]); 
                else if (j == N - 1) 
                    dp[i][j] = A[i][j] + Math.Min(dp[i - 1][j - 1],  
                                                 dp[i - 1][j]); 
                else
                    dp[i][j] = A[i][j] + Math.Min(dp[i - 1][j - 1],  
                                Math.Min(dp[i - 1][j], dp[i - 1][j + 1])); 
            } 
        } 
          
        // Find the minimum from the last row of dp 
        int res = dp[N - 1][0]; 
        for (int i = 1; i < N; i++) 
            res = Math.Min(res, dp[N - 1][i]); 
        return res; 
    }
}