Сколько существует различных путей из города A в город K?

Для решения задачи рассмотрим граф с вершинами A, B, В, Г, Д, Е, K, где каждая вершина обозначает город, а стрелки показывают возможное направление движения. Для подсчёта путей из A в K применим метод динамического программирования: 1. Обозначим количество путей из A в каждую вершину: Пусть dp[v] — количество путей в вершину v из вершины A. 2. Инициализируем: dp[A] = 1 (в саму вершину A существует один способ попасть). 3. Для остальных вершин: dp[v] = сумма dp[u] для всех u, из которых имеется путь к v. Применяя это правило, последовательно вычисляем значения для каждой вершины, пользуясь схемой дорог: - dp[B] = dp[A] = 1. - dp[Г] = dp[A] = 1. - dp[В] = dp[B] = 1. - dp[Д] = dp[B] = 1. - dp[Е] = dp[Г] = 1. - dp[K] = dp[В] + dp[Д] + dp[Е] = 1 + 1 + 1 = 3. Ответ: 3 пути.