На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?

Нам нужно найти число различных маршрутов в ориентированном графе (без циклов), например, используя метод динамического программирования. Предположим, что на рисунке каждая точка (город) имеет только входящие дороги от некоторых предыдущих городов, то есть получив схему можно последовательно «прокачать» значение числа маршрутов от начальной вершины A до нужной вершины (в задаче город с пометкой «3»).

Шаг 1. Обозначим для каждого города величину f(город) – число маршрутов из A в этот город. При этом f(A) = 1, так как существует тривиальный путь, который начинается и сразу находится в A.

Шаг 2...