Question on DP states for problem.

Правка en1, от nytemusik, 2020-07-21 02:38:36

Recently I was trying to solve the problem F. Two Bracket Sequences. In the editorial it was stated that a 3-dimensional DP with i (position on sequence s) j (position on sequence t) and bal (current number of open brackets) is needed for the solution. I cannot understand why a 2-dimensional DP would not be sufficient for the correct answer. If you are in state DP[i][j], you would always want to minimize the additional characters added to form the regular bracket sequence till this point. Effectively, the relationship between open brackets used in the 2 strings and additional brackets added is additive and you would always want to use previous open brackets in the strings before adding additional characters. My DP would just store a pair <minimum additional characters used, maximum balance for this state> at each position. Sorry if the question is not clear.

Теги #dp, #help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский nytemusik 2020-07-21 02:38:36 956 Initial revision (published)