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.