Почему это рекуррентное отношение динамического программирования верно?

Считайте, что у вас есть экран. Теперь мы можем сделать две операции на экране:

  1. Копировать содержимое на экране

  2. Вставьте скопированный контент на экран

Предположим, вначале буфер обмена пуст, а на экране один символ. Если у нас есть N операций, как мы можем напечатать максимальное количество символов на экране, используя N операций копирования и вставки?

Ответ DP[N]=max(2DP[N-2],3DP[N-3])

Но как нам получить вышеупомянутый результат? И почему приведенные ниже формулировки неверны?

  1. DP[N]=max(DP[N-1],2DP[N-2])

  2. DP[N]=2DP[N-2]

Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
1
0
22
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Объяснение правильного повторения

Имея операцию Nth как печать, N-1-я операция может быть либо копированием, либо вставкой.

  1. N-1-я копия, N-я вставка.
    Копирование в N-1 будет означать копирование dp[N-2] символов, поэтому общее количество здесь становится 2*dp[N-2]
  2. N-2-я копия, N-1-я вставка, N-я вставка.
    Копирование в N-2 будет означать копирование dp[N-3] символов, поэтому общее количество здесь становится 3*dp[N-3] (исходное dp[N-3] + вставлено дважды).
  3. N-3-я копия в 3 вставках не имеет смысла, так как вы можете получить один и тот же результат, выполнив шаг 1 дважды.

Таким образом, результат становится dp[N] = max(2*dp[N-2],3*dp[N-3]).

Проблема с повторением

  1. DP[N]=max(DP[N-1],2DP[N-2]) не будет работать, потому что нет возможности отследить, есть ли у вас N-я операция в виде копирования или вставки.
  2. DP[N]=2DP[N-2] пропускает случай двух последовательных вставок (подсказка: перечислены первые несколько значений в таблице dp, выясните случай для dp[5]:
i -> dp[i]
0      0
1      1
2      2
3      2
4      4
5      6

Другие вопросы по теме