Минимум ходов, чтобы сделать M и N равными путем многократного добавления делителей, кроме 1, с использованием динамического программирования.

Опубликовано: 26 Февраля, 2023

Даны два целых числа 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ