algorithm - 为什么这个动态规划递归关系是正确的？

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

解释正确的重现

如果第 N 操作为打印，则第 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