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

Решим задачу, используя метод динамического программирования. Обозначим количество путей из города А в город X как K(X). Будем последовательно вычислять количество путей до каждого города.

1. K(A) = 1 (начальное условие)
2. K(Б) = K(A) = 1 (так как из А в Б ведет одна дорога)
3. K(В) = K(A) = 1 (так как из А в В ведет одна дорога)
4. K(Г) = K(A) = 1 (так как из А в Г ведет одна дорога)
5. K(Д) = K(A) = 1 (так как из А в Д ведет одна дорога)
6. K(Е) = K(Б) = 1 (так как из Б в Е ведет одна дорога)
7. K(Ж) = K(Г) + K(Д) = 1 + 1 = 2 (так как в Ж ведут дороги из Г и Д)
8. K(K) = K(Е) + K(В) + K(Ж) = 1 + 1 + 2 = 4 (так как в K ведут дороги из Е, В и Ж)

Таким образом, существует 4 различных пути из города А в город К.

Ответ: 4