Minimum Falling Path Sum
Given an n x n matrix, return the minimum sum of any falling path through the 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.

30:00

Minimum Falling Path Sum
medium
Topics
Companies

Given an n x n matrix, return the minimum sum of any falling path through the 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.

Example 1:
Input: [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Constraints:

  • n==matrix.length==matrix[i].lengthn == \text{matrix.length} == \text{matrix}[i].\text{length}

  • 1≤n≤1001 \leq n \leq 100

  • −100≤matrix[i][j]≤100-100 \leq \text{matrix}[i][j] \leq 100

Input
arr =[[2,1,3],[6,5,4],[7,8,9]]

Initialize DP with first row values

Input Matrix
2
1
3
6
5
4
7
8
9
DP Table (Min Path Sum)
2
1
3
6
5
4
7
8
9
Variables
No variables to display
DepthFunction Call
Stack empty
0/7