- package main
- func main() {
- a := [][]int{ {3}, { 7, 4 }, { 2, 4, 6 }, { 8, 5, 9, 3 } }
- b := [][]int{
- {75},
- { 95, 64 },
- { 17, 47, 82 },
- { 18, 35, 87, 10 },
- { 20, 4, 82, 47, 65 },
- { 19, 1, 23, 75, 3, 34 },
- { 88, 2, 77, 73, 7, 63, 67 },
- { 99, 65, 4, 28, 6, 16, 70, 92 },
- { 41, 41, 26, 56, 83, 40, 80, 70, 33 },
- { 41, 48, 72, 33, 47, 32, 37, 16, 94, 29 },
- { 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14 },
- { 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57 },
- { 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48 },
- { 63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31 },
- { 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23 } }
- p018(a) // 23
- p018(b) // 1074
- }
- func p018(A [][]int) {
- max := make([]int, len(A[len(A)-1]))
- copy(max, A[len(A)-1])
- for i := len(A) - 2; i >= 0; i-- {
- for j := 0; j < len(A[i]); j++ {
- add := max[j]
- if add < max[j+1] { add = max[j+1] }
- max[j] = A[i][j] + add
- }
- }
- println(max[0])
- }
复制代码
|