Оглавление > Максимальная сумма пути
10.03.2023

Максимальная сумма пути

Начиная в вершине треугольника (см. пример ниже) и перемещаясь вниз на смежные числа, максимальная сумма до основания составляет 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 возможных маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов.

Решение (F#)

Примечание условия намекает на то, что решать прямым перебором не следует, значит придумаем другое решение.

  1. Вводим исходные данные в строку source
  2. Преобразуем в массив массивов целых чисел data
  3. Для каждого элемента каждой строки, начиная с предпоследней:
    • найдем максимум из смежных элементов следующей строки
    • прибавим максимум к текущему элементу
  4. таким образом, после обработки всех строк, первый элемент первой строки будет содержать максимальную сумму пути
  5. Выведем ответ
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