CODEWITHSUNDEEP
algorithmdynamic-programming
ErroR
ErroR

Reputation: 143

Why this dynamic programming recurrence relation is correct?

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]

Upvotes: 1

Views: 100

Answers (1)

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

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

Upvotes: 4

Related Questions