На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город T?
Картинка к вопросу
Наша цель – найти число различных путей из города A (А) в город T (Т) по направленным дорогам, то есть в получившемся ориентированном ациклическом графе. Один из распространённых способов – использовать метод динамического программирования, когда для каждой вершины (города) вычисляем число путей от неё до цели (Т), двигаясь «обратно» от Т к A.
Ниже приведён один из вариантов построения схемы (поскольку исходная схема не приведена в условии, но перечень городов и направление дорог типичны для подобных задач). Предположим, что схема имеет следующую структуру (на рисунке города со...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
