Help me understand the editorial for this DP question pls!

Revision en1, by _Siegefried, 2021-09-25 16:55:22

LINK to the problem

Its a previous edition "Codeagon" problem and I am trying to understand the editorial. I get the approach but it's my first time encountering a 4-D dp approach. I get the basic intuition behind the problem of subtracting solutions containing characters from only one string from all the solutions, but am unable to understand why we need a 4th state ("status" in editorial) at all as in calculating all possible solutions, how does it matter if I selected/skipped a character from A or from B previously, so why even keep a tab of it. I am probably looking at it wrong, so any help would mean a lot. Also, if a different approach comes to mind, pls do share it as well, thx!

Tags string, dynamic programming, codeagon

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English _Siegefried 2021-09-25 16:55:22 844 Initial revision (published)