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