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].length
  • 1 <= 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
}