## Algorithm

Problem Name: 931. Minimum Falling Path Sum

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)`.

Example 1:

```Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.
```

Example 2:

```Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.
```

Constraints:

• `n == matrix.length == matrix[i].length`
• `1 <= n <= 100`
• `-100 <= matrix[i][j] <= 100`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int minFallingPathSum(int[][] matrix) {
int minFallingSum = Integer.MAX_VALUE;
Integer[][] dp = new Integer[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
minFallingSum = Math.min(minFallingSum, findMinFallingPathSumHelper(matrix, 0, i, dp));
}
return minFallingSum;
}

private int findMinFallingPathSumHelper(int[][] matrix, int row, int col, Integer[][] dp) {
if (col < 0 || col == matrix.length) {
return Integer.MAX_VALUE;
}
if (row == matrix.length - 1) {
return matrix[row][col];
}
if (dp[row][col] != null) {
return dp[row][col];
}
int leftSum = findMinFallingPathSumHelper(matrix, row + 1, col, dp);
int middleSum = findMinFallingPathSumHelper(matrix, row + 1, col + 1, dp);
int rightSum = findMinFallingPathSumHelper(matrix, row + 1, col - 1, dp);
dp[row][col] = Math.min(leftSum, Math.min(middleSum, rightSum)) + matrix[row][col];
return dp[row][col];
}
}
``````
Copy The Code &

Input

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

Output

cmd
13

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minFallingPathSum = function(A) {
for (let i = 1, rows = A.length; i < rows; i++) {
for (let j = 0, cols = A[0].length; j < cols; j++) {
A[i][j] += Math.min(
getValueOrMax(A, i - 1, j - 1),
getValueOrMax(A, i - 1, j),
getValueOrMax(A, i - 1, j + 1)
);
}
}
return Math.min(...A[A.length - 1]);
};

function getValueOrMax(A, i, j) {
return A[i][j] !== undefined ? A[i][j] : Number.MAX_VALUE;
}
``````
Copy The Code &

Input

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

Output

cmd
13

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minFallingPathSum(self, A):
for i in range(1, len(A)):
for j in range(len(A)):
A[i][j] += min(A[i - 1][j and j - 1:j + 2])
return min(A[-1])
``````
Copy The Code &

Input

cmd
matrix = [[-19,57],[-40,-5]]

Output

cmd
-59

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0931_MinimumFallingPathSum
{
public int MinFallingPathSum(int[][] A)
{
int N = A.Length;
if (N == 1) return A[0][0];

var path = new int[N, N];
for (int i = 0; i < N; i++)
path[0, i] = A[0][i];

var min = int.MaxValue;
for (int row = 1; row < N; row++)
for (int col = 0; col < N; col++)
{
var above = path[row - 1, col];
if (col > 0)
above = Math.Min(above, path[row - 1, col - 1]);
if (col < N - 1)
above = Math.Min(above, path[row - 1, col + 1]);

path[row, col] = above + A[row][col];

if (row == N - 1)
{
min = Math.Min(min, path[row, col]);
}
}

return min;
}
}
}
``````
Copy The Code &

Input

cmd
matrix = [[-19,57],[-40,-5]]

Output

cmd
-59