Начиная в вершине треугольника (см. пример ниже) и перемещаясь вниз на смежные числа, максимальная сумма до основания составляет 23.
3
7 4
2 4 6
8 5 9 3
То есть, 3 + 7 + 4 + 9 = 23.
Найдите максимальную сумму пути от вершины до основания следующего треугольника:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
Примечание: Так как в данном треугольнике всего 16384 возможных маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов.
Примечание условия намекает на то, что решать прямым перебором не следует, значит придумаем другое решение.
let source = "75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
let data = source.Split '\n' |> Array.map (fun line -> line.Split ' ' |> Array.map int)
for i in data.Length - 2..-1..0 do
for j in 0..data[i].Length - 1 do
data[i][j] <- data[i][j] + max (data[i+1][j]) (data[i+1][j+1])
let answer = data[0][0]
printfn $"the answer is {answer}" //the answer is 1074
1074
995 999
818 900 935
704 801 853 792
686 640 766 731 782
666 614 636 684 660 717
647 501 613 609 533 657 683
559 499 479 536 514 526 594 616
460 434 419 475 508 470 510 524 487
419 365 393 387 419 425 430 376 454 322
378 317 231 321 354 372 393 354 360 293 247
325 246 187 178 256 329 273 302 263 242 193 233
255 235 154 150 140 179 256 209 224 172 174 176 148
125 164 102 95 112 123 165 128 166 109 122 147 100 54
4 62 98 27 23 9 70 98 73 93 38 53 60 4 23