为什么这个动态规划递推关系是正确的呢？

Question

假设你有一个屏幕。现在我们可以在屏幕上做两个操作：

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]

Answer 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 table 中的前几个值，找出 dp[5] 的情况：

i -> dp[i]
0      0
1      1
2      2
3      2
4      4
5      6