Метод динамического программирования применим в случае, если процесс решения задачи можно представить ориентированным графом, имеющим один исток, один сток и не содержащим циклов.
1) Представьте себе частично решенную задачу и попытайтесь описать состояние объекта в этом промежуточном состоянии (независимо от действий, которые привели к этому состоянию).
2) Каждому такому состоянию сопоставьте вершину графа.
3) Попытайтесь формализовать переходы из одного состояния в другое (из одной вершины к другой). Обычно это несложно, но бывают исключения:
3') Если по выбранному объему данных, описывающему состояние, невозможно однозначно определить список доступных действий, значит, Вы включили в описание состояния не всю требуемую информацию - Вам необходимо расширить пространство состояний (обычно этот шаг влечет увеличение кол-ва вершин в графе в несколько раз).
4) Если поиск оптимального пути в получившемся графе разрешим методом динамического программирования за вычислительно разумное время/память, то Вы достигли своей цели. Если нет - подумайте, нет ли возможности свернуть граф (уменьшить колво данных, определяющих вершину).
