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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
package main
import "fmt"
func min(a, b int) int {
if a < b {
return a
}
return b
}
func min3(a, b, c int) int {
min := a
if b < min {
min = b
}
if c < min {
min = c
}
return min
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func getRowMin(row []int) int {
min := row[0]
for i := 1; i < len(row); i++ {
if row[i] < min {
min = row[i]
}
}
return min
}
func dumpMatrix(matrix [][]int) {
for i := 0; i < len(matrix[0]); i++ {
for j := 0; j < len(matrix[0]); j++ {
fmt.Print(matrix[i][j], " ")
}
fmt.Println()
}
}
func minFallingPathSum(matrix [][]int) int {
for i := 1; i < len(matrix[0]); i++ {
for j := 0; j < len(matrix[0]); j++ {
// matrix[i][j] += min(matrix[i-1][j], min(matrix[i-1][max(0, j-1)], matrix[i-1][min(len(matrix[0])-1, j+1)]))
matrix[i][j] += min3(matrix[i-1][j], matrix[i-1][max(0, j-1)], matrix[i-1][min(len(matrix[0])-1, j+1)])
}
}
// dumpMatrix(matrix)
return getRowMin(matrix[len(matrix[0])-1])
}
func main() {
fmt.Println(minFallingPathSum([][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}))
fmt.Println(minFallingPathSum([][]int{{2, 1, 3}, {6, 5, 4}, {7, 8, 9}}))
}
|
