Минимум ходов, чтобы сделать M и N равными путем многократного добавления делителей, кроме 1, с использованием динамического программирования.
Даны два целых числа N и M , задача состоит в том, чтобы вычислить минимальное количество ходов для замены N на M , где За один ход можно прибавить любой делитель текущего значения N к самому N , кроме 1. Выведите «-1». " , если это невозможно.
Пример :
Input: N = 4, M = 24
Output: 5
Explanation: The given value of N can be converted into M using the following steps: (4)+2 -> (6)+2 -> (8)+4 -> (12)+6 -> (18)+6 -> 24. Hence, the count of moves is 5 which is the minimum possible.Input: N = 4, M = 576
Output: 14
Подход BFS: данная проблема уже обсуждалась в наборе 1 этой статьи, в котором для решения данной проблемы используется обход в ширину.
Подход : в этой статье рассматривается другой подход, основанный на динамическом программировании. Ниже приведены шаги, которые необходимо выполнить:
- Создайте одномерный массив dp[] , где dp[i] хранит минимальное количество операций для достижения i из N . Изначально dp[N+1… M] = {INT_MAX} и dp[N] = 0 .
- Перебрать диапазон [N, M] , используя переменную i , и для каждого i перебрать все факторы заданного числа i . Для фактора X отношение DP можно определить следующим образом:
dp[i + X] = min( dp[i], dp[i + X])
- Значение, хранящееся в dp[M], является требуемым ответом.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O((M – N)*√(M – N))
Вспомогательное пространство: O(M)