Динамическое программирование

Компьютеры программирование информатика алгоритм

Напишите решение задачи треугольник:
есть треугольник чисел. Нужно написать программу, которая определяет максимальную сумму, которую можно собрать, пройдя от вершины до любой точки основы
Ответы:
Действуй таким образом:
В каждое число можно попасть из любых двух над ним (если над ним два, а не одно).
Двигайся сверху вниз и заменяй каждое число на максимальный путь к нему с вершины.
То есть, допустим:
     1
  3    5
2    6    4
Заменим 3 и 5 на 4 и 6 (4 = 1 + 3, 6 = 1 + 5).
     1
  4    6
И дальше:
     1
  4     6
6   12   10
Ищем в последней строке максимальное - 12, это и есть ответ.
На Паскале можно реализовать так:


13 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.