Help in dp problem, "wrong brackets"

Revision en1, by atlasworld, 2019-05-26 08:30:46

The problem wrong brackets asks you to find k_th lexographically incorrect bracket sequence.

Editorial uses dynamic programming method dp[i][j] = the number of strings (of length 2N that contain N open brackets and N closed brackets) that are not correct, but their prefix of length i is correct and it contains j more open brackets than closed ones.

but how can bracket sequence be correct when i is of odd length. since i can be odd how to make dp transistions on them. The editorial did almost same for both even and odd length i prefix. i didn't understood it. can someone please explain the approach.

Thanks !


  Rev. Lang. By When Δ Comment
en1 English atlasworld 2019-05-26 08:30:46 799 Initial revision (published)