» » »

=11. Методика динамического программирования (Определение. Алгоритмы и задачи: вычисление биномиальных коэффициентов, алгоритм Флойда)

способ решения сложных задач - путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.

Вычисление биномиальных коэффициентов

src=img/11-1.jpg

Алгоритм Флойда

src=img/11-2.jpg
src=img/11-3.jpg

Временная эффективность-кубическая.


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.