Спочатку обчислимо всі mi,i+1 за i=1, … , n-1. Очевидно, mi,i+1=si-1×si×si+1. Запам'ятавши їх, обчислимо mi,i+2і також запам'ятаємо. Потім обчислимо всі mi,i+3 тощо, збільшуючи різницю d між другим та першим індексами, поки не дійдемо до m1n. При цьому ми обчислюємо mij за формулою
mij ={mik+mk+1,j+si-1×sk×sj}
Наведений алгоритм уточнюється таким чином:
for i:=1 to n-1 do m[i, i+1]:=s[i-1]*s[i]*s[i+1];
for d:=1 to n-1 do
for i:=1 to n-d do
begin
j:=i+d;
У m[i, j] запам'ятати мінімальне зі значень
m[i,k]+m[k+1,j]+s[i-1]*s[k]*s[j] по всіх k=i+1, …, j-1
end
{m[1, n] – шукане значення}
Безпосередньо за алгоритмом неважко переконатися, що оцінкою його складності є O(n3).-
Підіб'ємо підсумок. В обох прикладах ми будували послідовності – шляхи на циліндрі або послідовності дужок. Характерним для них є те, що, кажучи неформально, коли зафіксовано якийсь компонент у їх середині, то оптимальний вибір компонентів у початку не впливає на оптимальний вибір у кінці, і навпаки. Саме ця незалежність позбавляє необхідності перебирати всі можливі послідовності і забезпечує складність наведених алгоритмів порядку O(mn) та O(n3) відповідно.
У задачі про три станки такої незалежності рішень на початку їх послідовності та в її кінці немає. Саме це змушує перебирати всі можливі послідовності та зумовлює незастосовність принципу оптимальності. Для цієї задачі немає алгоритмів, які б дозволяли будувати розв'язок із незалежних частин подібно до задачі про добуток матриць.
Існує величезний клас задач, розв'язки яких є послідовностями заданого вигляду, причому їх початок і кінець взаємозалежні. Для таких задач побудовано алгоритми складності не менше O(2n), де n – це величина, що характеризує розмір вхідних даних задачі. Але для них досі не побудовано алгоритмів, складність яких можна було б оцінити поліноміальною функцією від n. Поки що не доведено, що таких алгоритмів узагалі не можна побудувати, але саме до такої думки схиляються майже всі, хто мав справу з цими задачами.
Серед задач, розв'язок яких будується перебиранням варіантів, виділяються так звані NP-складні та NP-повні задачі. Обсяг і характер цієї книжки не дозволяють розпочинати знайомство з ними, тому зацікавлений читач може подивитися в книги [АХУ, РНД, ГД].