14
правок
Изменения
Нет описания правки
== Решение ==
Данная задача решается с использованием принципа оптимальности на подотрезке[http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D0.BE.D0.B4.D0.BE.D1.82.D1.80.D0.B5.D0.B7.D0.BA.D0.B0.D1.85]. Введём матрицу <tex>d</tex> размером <tex>n \times n</tex>, где <tex>d[i][j]</tex> будет равен максимальному значению, достигаемому на подотрезке <tex dpi = "130">a_i, a_{i+1}, \dots, a_j</tex>.
Получаем следующие соотношения: <br />
* <tex>d[i][i] = a_i </tex><br />
== Источники ==
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4
* [http://ru.wikipedia.org/wiki/Динамическое_программирование Википедия]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
