Medium

Minimum Falling Path Sum

LAB

Given a square matrix, return the minimum sum of a falling path moving down one row and at most one column sideways each step.

EXAMPLES

Example 1

Input
{
  "matrix": [
    [
      2,
      1,
      3
    ],
    [
      6,
      5,
      4
    ],
    [
      7,
      8,
      9
    ]
  ]
}

Output
13

FUNCTION SHAPE

matrix: intMatrix→int

SOLUTION NOTE

From each cell, can move to 3 cells below. Take minimum path.

Reveal reference solution +

pythonREFERENCE

def minFallingPathSum(self, matrix: List[List[int]]) -> int:
    n = len(matrix)

    @cache
    def dp(i, j):
        if j < 0 or j >= n:
            return float('inf')
        if i == n - 1:
            return matrix[i][j]
        return matrix[i][j] + min(dp(i + 1, j - 1), dp(i + 1, j), dp(i + 1, j + 1))

    return min(dp(0, j) for j in range(n))

TimeO(n²)

SpaceO(n²)

Open on LeetCode ↗