Задача: 397. Integer Replacement Сложность: medium К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1. Пример: Input: n = 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1 👨‍💻 Алгоритм: 1⃣Начните с данного числа n и выполните одну из следующих операций: Если n четное, замените n на n / 2. Если n нечетное, замените n на n + 1 или n - 1. 2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов. 3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат. 😎 Решение: class Solution: def integerReplacement(self, n: int) -> int: def helper(n, memo): if n == 1: return 0 if n in memo: return memo[n] if n % 2 == 0: memo[n] = 1 + helper(n // 2, memo) else: memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo)) return memo[n] return helper(n, {}) Ставь 👍 и забирай 📚 Базу знаний