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

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