Минимальное количество заданных операций, необходимое для уменьшения числа до 2
Дана натуральное число N , задача состоит в том, чтобы уменьшить N до 2 , выполнив следующие операции минимальное количество раз:
- Операция 1: Разделите N на 5 , если N точно делится на 5 .
- Операция 2: вычесть 3 из N .
Если это невозможно, выведите -1 .
Примеры:
Input: N = 28
Output: 3
Explanation: Operation 1: Subtract 3 from 28. Therefore, N becomes 28 – 3 = 25.
Operation 2: Divide 25 by 5. Therefore, N becomes 25 / 5 = 5.
Operation 3: Subtract 3 from 5. Therefore, N becomes 5 – 3 = 2.
Hence, the minimum number of operations required is 3.Input: n=10
Output: 1
Explanation: Operation 1: Divide 10 by 5, so n becomes 10/5=2.
Hence, the minimum operations required is 1.
Наивный подход: идея состоит в том, чтобы рекурсивно вычислить минимальное количество необходимых шагов.
- Если число не делится на 5, то вычесть 3 из n и повторить для измененного значения n, добавив 1 к результату.
- В противном случае сделайте два рекурсивных вызова, один вычитая 3 из n, а другой опуская n на 5, и возвращайте тот, у которого минимальное количество операций, добавляя 1 к результату.
Временная сложность: O( 2n )
Вспомогательное пространство: O(1)
Эффективный подход. Чтобы оптимизировать описанный выше подход, идея заключается в использовании динамического программирования. Выполните следующие действия, чтобы решить эту проблему.
- Создайте массив, скажем, dp[n+1] для хранения минимальных операций и инициализируйте все записи с помощью INT_MAX, где dp[i] хранит минимальное количество шагов, необходимых для достижения 2 из i .
- Обработайте базовый случай, инициализировав dp[2] как 0 .
- Итерировать в диапазоне [2, n], используя переменную i
- Если значение i*5 ≤ n , то обновите dp[i*5] до минимума dp[i*5] и dp[i]+1 .
- Если значение i+3 ≤ n , то обновите dp[i+3] до минимума dp[i+3] и dp[i]+1 .
- Выведите значение dp[n] как результат.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(n)
Вспомогательное пространство: O(n)