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
if j > 0:
if j < len(A)-1:

# update the current value in the dp array

# 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;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]