Динамика и BFS

Динамическое программирование решает задачу через ответы на подзадачи и запоминает их, чтобы не считать дважды. Поиск в ширину (BFS) обходит граф слоями с помощью очереди и находит кратчайший путь в графе без весов за O(V + E). Огромные ответы часто просят по модулю 10⁹ + 7.