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

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

Имея операцию 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