Array
Dynamic Programming
Matrix
Description
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
Solutions
Solution 1
Python3 Java C++ Go TypeScript
class Solution :
def minFallingPathSum ( self , matrix : List [ List [ int ]]) -> int :
n = len ( matrix )
f = [ 0 ] * n
for row in matrix :
g = [ 0 ] * n
for j , x in enumerate ( row ):
l , r = max ( 0 , j - 1 ), min ( n , j + 2 )
g [ j ] = min ( f [ l : r ]) + x
f = g
return min ( f )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public int minFallingPathSum ( int [][] matrix ) {
int n = matrix . length ;
var f = new int [ n ] ;
for ( var row : matrix ) {
var g = f . clone ();
for ( int j = 0 ; j < n ; ++ j ) {
if ( j > 0 ) {
g [ j ] = Math . min ( g [ j ] , f [ j - 1 ] );
}
if ( j + 1 < n ) {
g [ j ] = Math . min ( g [ j ] , f [ j + 1 ] );
}
g [ j ] += row [ j ] ;
}
f = g ;
}
// return Arrays.stream(f).min().getAsInt();
int ans = 1 << 30 ;
for ( int x : f ) {
ans = Math . min ( ans , x );
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
int minFallingPathSum ( vector < vector < int >>& matrix ) {
int n = matrix . size ();
vector < int > f ( n );
for ( auto & row : matrix ) {
auto g = f ;
for ( int j = 0 ; j < n ; ++ j ) {
if ( j ) {
g [ j ] = min ( g [ j ], f [ j - 1 ]);
}
if ( j + 1 < n ) {
g [ j ] = min ( g [ j ], f [ j + 1 ]);
}
g [ j ] += row [ j ];
}
f = move ( g );
}
return * min_element ( f . begin (), f . end ());
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 func minFallingPathSum ( matrix [][] int ) int {
n := len ( matrix )
f := make ([] int , n )
for _ , row := range matrix {
g := make ([] int , n )
copy ( g , f )
for j , x := range row {
if j > 0 {
g [ j ] = min ( g [ j ], f [ j - 1 ])
}
if j + 1 < n {
g [ j ] = min ( g [ j ], f [ j + 1 ])
}
g [ j ] += x
}
f = g
}
return slices . Min ( f )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 function minFallingPathSum ( matrix : number [][]) : number {
const n = matrix . length ;
const f : number [] = new Array ( n ). fill ( 0 );
for ( const row of matrix ) {
const g = f . slice ();
for ( let j = 0 ; j < n ; ++ j ) {
if ( j > 0 ) {
g [ j ] = Math . min ( g [ j ], f [ j - 1 ]);
}
if ( j + 1 < n ) {
g [ j ] = Math . min ( g [ j ], f [ j + 1 ]);
}
g [ j ] += row [ j ];
}
f . splice ( 0 , n , ... g );
}
return Math . min (... f );
}
GitHub