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].length1 <= 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];
}
}
Input
Output
#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;
}
Input
Output
#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])
Input
Output
#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;
}
}
}
Input
Output