Способ решения сложных задач путём разбиения их на более простые подзадачи

1.

2.

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

3.

—
это простое запоминание результатов решения тех
подзадач, которые могут повторно встретиться в
дальнейшем.
включает в себя переформулирование сложной
задачи в виде рекурсивной последовательности
более простых подзадач.

4.

Словосочетание
впервые было
использовано в 1940-х годах Р. Беллманом.
Первоначально эта область была основана,
как системный анализ и инжиниринг, которая
была признана IEEE.
Р. Беллман
Слово
в данном контексте скорее
означает оптимальную последовательность действий для
получения решения задачи.

5.

X1
S0
S1
X2
Xk-1
Sk-1
Xk
Sk
Xk+1
Xn-1
Xn
Sn-1
Sn