Минимальное количество операций суммы и по модулю с использованием заданных чисел для достижения цели

Учитывая число N , массив arr[] и целевое число K , задача состоит в том, чтобы найти минимальное количество ходов для достижения K , выбрав любой элемент массива и изменив N на (N + arr[i]) mod 100000 в каждом шаг.

Примеры:

Input: N = 99880, K = 89, arr = {100, 3}
Output: 5
Explanation: Number “100” is used 2 times and the number “3” is pushed 3 times, resulting in K from N

Input: N = 10000, K = 10004, arr = {1}
Output: 4

Подход: Вышеупомянутая проблема может быть решена с помощью динамического программирования, поскольку оно имеет перекрывающиеся подзадачи и оптимальную подструктуру. Инициализируйте таблицу dp , где dp[i] хранит минимальные ходы, необходимые для достижения состояния i на N, а dp[target] будет требуемым ответом. Из каждого arr[i] найдите все достижимые состояния и минимизируйте значение dp . Выполните следующие шаги для подхода:

• Инициализируйте массив, скажем, dp[] для хранения минимальных ходов, необходимых для достижения состояния i.
• Перебираем массив arr и проверяем каждую позицию текущего числа N как x :
  • если dp[x] равно -1, продолжаем.
  • в противном случае повторяйте цикл while до тех пор, пока dp[ next] не станет равным -1 или dp[next] не станет больше, чем dp[x] + 1 , и обновите next как (x+buttons[i])%100000 и dp[next] как dp[ х]+ 1 .
• Наконец, верните значение dp[target].

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M)
Вспомогательное пространство: O(N), поскольку занято N дополнительного пространства.