1

Consider you have a screen. Now we can do two operations on the screen:

  1. Copy content on the screen

  2. Paste copied content on the screen

Suppose at the beginning, the clipboard is empty and there is one character on the screen. If we have N operations, how we can print the maximum number of characters on the screen using N operations of copy and pastes?

The answer is DP[N]=max(2DP[N-2],3DP[N-3])

But how do we get the above result? And why below formulations aren't correct?

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

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

Improve this question

1 Answer 1

Reset to default
4

Explaining the correct recurrence

Having the Nth operation as print, the N-1th operation could be either copy or paste.

  1. N-1th copy, Nth paste.
    Copying at N-1 would mean copying dp[N-2] characters, so the total here becomes 2*dp[N-2]
  2. N-2th copy,N-1th paste, Nth paste.
    Copying at N-2 would mean copying dp[N-3] characters, so the total here becomes 3*dp[N-3] (original dp[N-3] + pasted twice).
  3. N-3th copy at 3 pastes wouldn't make sense, since you could get the same result via step 1 twice.

So the result becomes dp[N] = max(2*dp[N-2],3*dp[N-3]).

Issue with your recurrence

  1. DP[N]=max(DP[N-1],2DP[N-2]) wouldn't work because there's no way to track if you have the Nth operation as a copy or paste.
  2. DP[N]=2DP[N-2] misses the case of two consecutive pastes (hint: First few values in the dp table are listed, figure out the case for dp[5]:
i -> dp[i]
0      0
1      1
2      2
3      2
4      4
5      6
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

@user355834 Assuming x characters at the first copy, CPPP will give 4x chars, and CPCP will also have the same result

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.