650. 2-клавишная клавиатура

Сложность: Средняя

Темы: Математика, динамическое программирование

На экране блокнота только одна буква «А». Для каждого шага вы можете выполнить одну из двух операций в этом блокноте:

• Копировать все: вы можете скопировать все символы, представленные на экране (частичное копирование запрещено).
• Вставить: можно вставить символы, скопированные в последний раз.

Дано целое число n, верните минимальное количество операций, чтобы получить символ 'A' ровно n раз на экране.

Пример 1:

• Ввод: n = 3
• Вывод: 3
• Пояснение: Изначально у нас есть один символ «А».
  • На шаге 1 мы используем операцию «Копировать все».
  • На шаге 2 мы используем операцию вставки, чтобы получить «AA».
  • На шаге 3 мы используем операцию вставки, чтобы получить «AAA».

Пример 2:

• Ввод: n = 1
• Вывод: 0

Пример 3:

• Ввод: n = 10
• Выход: 7

Пример 2:

• Ввод: n = 24
• Вывод: 9

Ограничения:

• 1

Намекать:

1. Сколько символов может находиться в буфере обмена на последнем шаге, если n = 3? п = 7? п = 10? n = 24?

Решение:

Нам нужно найти минимальное количество операций, чтобы на экране появилось ровно n символов «А». Для этого мы воспользуемся подходом динамического программирования.

1. Понимание проблемы:

   • Мы начинаем с одной буквы «А» на экране.
   • Мы можем либо «Копировать все» (что копирует текущее содержимое экрана), либо «Вставить» (что вставляет последнее скопированное содержимое).
   • Нам нужно определить минимальное количество операций, необходимых для того, чтобы на экране появилось ровно n символов «A».

2. Подход к динамическому программированию:

   • Используйте массив динамического программирования (DP) dp, где dp[i] представляет минимальное количество операций, необходимых для получения ровно i символов на экране.
   • Инициализируйте dp[1] = 0, так как требуется 0 операций, чтобы на экране появилась одна буква «А».
   • Для каждого количества символов i от 2 до n вычислите минимальные операции, проверив каждый делитель i. Если i делится на d, то:
     • Количество операций, необходимых для достижения i, представляет собой сумму операций для достижения d плюс операций, необходимых для умножения d, чтобы получить i.

3. Шаги для решения:

   • Инициализировать массив DP с помощью INF (или большого числа) для всех значений, кроме dp[1].
   • Для каждого i от 2 до n переберите возможные делители i и обновите dp[i] на основе операций, необходимых для достижения i путем копирования и вставки.

Давайте реализуем это решение на PHP: 650. 2-клавишная клавиатура

Объяснение:

• Инициализация: dp инициализируется большим числом (PHP_INT_MAX), чтобы представить изначально недостижимое состояние.
• Проверка делителя: Для каждого числа i проверьте все делители d. Обновите dp[i], рассмотрев операции, необходимые для достижения d, а затем умножив, чтобы получить i.
• Вывод: Результатом является значение dp[n], которое дает минимальное количество операций, необходимых для получения ровно n символов на экране.

Этот подход гарантирует, что мы эффективно вычислим минимальные операции для заданных ограничений.

Контактные ссылки

Если эта серия оказалась для вас полезной, поставьте репозиторию звездочку на GitHub или поделитесь публикацией в своих любимых социальных сетях?. Ваша поддержка очень много значит для меня!

Если вы хотите больше такого полезного контента, подписывайтесь на меня:

• LinkedIn
• GitHub