931. Minimum Falling Path Sum
Medium
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
func minFallingPathSum(matrix [][]int) int {
if len(matrix) == 1 {
return matrix[0][0]
}
for i := 1; i < len(matrix); i++ {
for j := 0; j < len(matrix[0]); j++ {
if j == 0 {
matrix[i][j] += min(matrix[i - 1][j], matrix[i - 1][j + 1])
} else if j == len(matrix[0]) - 1 {
matrix[i][j] += min(matrix[i - 1][j], matrix[i - 1][j - 1])
} else {
matrix[i][j] += min(matrix[i - 1][j], min(matrix[i - 1][j + 1], matrix[i - 1][j - 1]))
}
}
}
min := matrix[len(matrix) - 1][0]
for i := 0; i < len(matrix[0]); i++ {
if matrix[len(matrix) - 1][i] < min {
min = matrix[len(matrix) - 1][i]
}
}
return min
}
func min(a, b int) int {
if a < b { return a }
return b
}