Изменения

| '''4''' || - || - || - || 0

|}

Матрица p будет выглядеть следующим образом: <br />

{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"

Ответ равен 2.

==Источники==

* [http://en.wikipedia.org/wiki/Optimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]

[[Категория: Динамическое программирование ]]