Считайте, что у вас есть экран. Теперь мы можем сделать две операции на экране:
Копировать содержимое на экране
Вставьте скопированный контент на экран
Предположим, вначале буфер обмена пуст, а на экране один символ. Если у нас есть N операций, как мы можем напечатать максимальное количество символов на экране, используя N операций копирования и вставки?
Ответ
DP[N]=max(2DP[N-2],3DP[N-3])
Но как нам получить вышеупомянутый результат? И почему приведенные ниже формулировки неверны?
DP[N]=max(DP[N-1],2DP[N-2])
DP[N]=2DP[N-2]
Имея операцию Nth
как печать, N-1
-я операция может быть либо копированием, либо вставкой.
N-1
-я копия, N
-я вставка.N-1
будет означать копирование dp[N-2]
символов, поэтому общее количество здесь становится 2*dp[N-2]
N-2
-я копия, N-1
-я вставка, N
-я вставка.N-2
будет означать копирование dp[N-3]
символов, поэтому общее количество здесь становится 3*dp[N-3]
(исходное dp[N-3]
+ вставлено дважды).N-3
-я копия в 3 вставках не имеет смысла, так как вы можете получить один и тот же результат, выполнив шаг 1 дважды.Таким образом, результат становится dp[N] = max(2*dp[N-2],3*dp[N-3])
.
DP[N]=max(DP[N-1],2DP[N-2])
не будет работать, потому что нет возможности отследить, есть ли у вас N
-я операция в виде копирования или вставки.DP[N]=2DP[N-2]
пропускает случай двух последовательных вставок (подсказка: перечислены первые несколько значений в таблице dp
, выясните случай для dp[5]
:i -> dp[i]
0 0
1 1
2 2
3 2
4 4
5 6