Динамическое Программирование в Примерах и Задачах
Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
- Разбиение задачи на подзадачи меньшего размера.
- Использование полученного решения подзадач для конструирования решения исходной задачи.
Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).
Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи, F3=F2+F1{\displaystyle F_{3}=F_{2}+F_{1}} и F4=F3+F2{\displaystyle F_{4}=F_{3}+F_{2}} — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали F2{\displaystyle F_{2}} дважды. Если продолжать дальше и посчитать F5{\displaystyle F_{5}}, то F2{\displaystyle F_{2}} посчитается ещё два раза, так как для вычисления F5{\displaystyle F_{5}} будут нужны опять F3{\displaystyle F_{3}} и F4{\displaystyle F_{4}}. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.
@Antionah Margaritell: может тогда перейти на какой либо язык программирования, функционирующий на базе ХР-бейсик, фортран.