На рисунке представлена схема дорог, связывающих города E, A, B, C, D, F, G, H, K, J, I, L. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города E в город L, проходящих через город K?
Решать будем динамикой.
Закрасим нужный город красным.
Цветом отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все цветные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.
Нужно понимать, что в город E можно попасть одним путём: собственно, никуда не уходить из города E.
Красным отметим только те дороги, которые так или иначе ведут в красный город. Не будем отмечать вовсе те дороги, которые никак не ведут в него. Напишем зелёным цветом над красным городом кол-во различных путей в него. Теперь мы можем оперировать только им.
Итого получается, что в пункт L ведут 24 различных пути.