Количество способов добраться до начального узла после прохождения ровно K ребер в полном графе
Учитывая полный граф, имеющий N узлов и N*(N-1)/2 ребер и положительное целое число K , задача состоит в том, чтобы найти количество способов, если вы начинаете с узла 1 и заканчиваете в том же узле, если ровно K ребер надо пройти.
Input: N = 4, K = 3
Output: 6
Explanation: The possible ways are-
1→2→3→1
1→2→4→1
1→3→2→1
1→3→4→1
1→4→2→1
1→4→3→1Input: N = 5, K = 3
Output: 12
Наивный подход: самый простой подход к решению этой проблемы - пройти от каждого ребра из текущей вершины, что приведет к экспоненциальному времени решения.
Временная сложность: O(N^N)
Вспомогательное пространство: O(N) из-за стека в рекурсивном вызове функции.
Эффективный подход: эта проблема имеет свойство перекрывающихся подзадач и свойство оптимальной подструктуры. Так что эту проблему можно решить с помощью динамического программирования. Как и в других типичных задачах динамического программирования (DP), повторного вычисления одних и тех же подзадач можно избежать, создав временный массив, в котором хранятся результаты подзадач. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте массив dp[] , где dp[i] хранит количество способов добраться до i -го узла, и инициализируйте dp[0] как 1.
- Выполните итерацию в диапазоне [1, K], используя переменную i , и выполните следующие шаги:
- Инициализируйте переменную numWays как 0 , чтобы хранить количество способов добраться до всех узлов.
- Выполните итерацию в диапазоне [0, N-1], используя переменную j, затем добавьте dp[j] в numWays.
- Выполните итерацию в диапазоне [0, N-1], используя переменную j, затем обновите значение dp[j] как максимум dp[j] и numWays — dp[j] .
- После выполнения вышеуказанных шагов выведите dp[0] в качестве ответа.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N×K)
Вспомогательное пространство: O(N)